找出一个字符串中最大重复子串

assiss

把字符串当成两个一样的串来考虑，一个串固定，另一个串划动(象拉链一样)，每一个次都取最大匹配串。。。
这样比较清楚，不用考虑很多复杂的东西，但效率不是很高，o(n*n)

cjaizss

拉动n次，每个长度要有n长度的字符串去拉动，o(n^3)

yzc2002

对于不连续的情况，这个也是O(n*n)的

1. int strmatch(char *str, char *match)
   
2. {
   
3.     int len = strlen(str), i, j, k;
   
4.     int first, second, max=0;
   
5.     int curr=0, curr_max=0;
   
6.     int tmp_max, tmp;
   
7.     for(i=1; i<len; i++)
   
8.     {
   
9.         if(str[curr+curr_max] == str[i] && curr_max < (i - curr + 1) >> 1 )
   
10.         {
    
11.             curr_max++;
    
12.             if(curr_max > max)
    
13.             {
    
14.                 max = curr_max;
    
15.                 first = curr;
    
16.                 second = i - curr_max + 1;
    
17.             }
    
18.         }
    
19.         else
    
20.         {
    
21.             i += max - curr_max;
    
22.             tmp_max = 0;
    
23.             curr_max = 0;
    
24.             for(j = i - 1; j >= tmp_max && str[i] != str[j]; j--);
    
25.             while(j >= tmp_max) {
    
26.                 tmp = j;
    
27.                 for(k=i-1, j--; k > tmp && j >= 0 && str[k] == str[j]; k--, j--);
    
28.                 tmp_max = i - k;
    
29.                 if(tmp_max > curr_max) {
    
30.                     curr_max = tmp_max;
    
31.                     curr = j+1;
    
32.                 }
    
33.                 for(; j >= tmp_max && str[i] != str[j]; j--);
    
34.             }
    
35.         }
    
36.     }
    
37.     memcpy(match, str+first, max);
    
38.     match[max] = 0;
    
39.     printf("first=%d, second=%d, max=%dn", first, second, max);
    
40. }
    

复制代码

noips

读入t串
利用kmp的next函数，并且设置一个max记录长度k.
最后从t串的开始到max-1输出最大重复子串

嘿嘿 我是学生~不过这道题已经解决~时间复杂程度是平方级~

效率十分高~举例  输入 ATATACG 输出ATA max为4