eg:
input aabcdabcde
output abcd
首先懂kmp的请回顾下kmp的next数组的求法,不懂得话就去自己看看
a a b c d a b c d e
-1 0 1 0 0 0 1 0 0 0
大家也许就说了这有麽用呢...对是没用
a b c d a b c d e
-1 0 0 0 0 1 2 3 4
ok看到没,如果是下面这样情况的话就可以了....
第一种情况,只要i++就可以变成二了....主要的循环就是
for(i=0;i
然后对str+i,求next,在找出最大的next[],如果max
大家也许对这里的i
看下intput: aaa
这样的直接一次循环就搞定了,当然这里会有点小问题如果输入aba的
如果是abcabc,最后还必须加1,废话了这么多,也许还是直接看程序易懂些
|
#include <stdio.h>
#include <stdlib.h>
int kmp_next(char* s, int next[])
{
int i = 0;
int k = -1;
int len = strlen(s);
next[i] = k;
while(i<len-1)
{
if(k==-1 || s[i]==s[k])
{
i++;
k++;
next[i] = k;
}
else
k = next[k];
}
}
int find_kmp_max(int next[], int n, int* index)
{
int max = next[0];
while(n>0)
{
if(next[n-1]>max)
{
*index = n;
max = next[n-1];
}
n--;
}
return max;
}
int getmax_substr(char* str, int* pos, int* max_sub_len)
{
int len = strlen(str);
int max = 0;
int i;
int index;
int* next = (int*)malloc(sizeof(int)*len);
*max_sub_len = 0;
for(i=0;i<len-2;i++)
{
kmp_next(str+i, next);
max = find_kmp_max( next, len-i, &index);
if(max>*max_sub_len)
{
*max_sub_len = max;
//if(index == len)
if((index == len) && (*(str+len-1) == *(str+i+max)))
*max_sub_len += 1;
*pos = i+1;
}
}
free(next);
}
int main(int argc, char *argv[])
{
//char* str = "aabcdabcde";
char* str = "aba";
int pos = 0;
int max_sub_len = 0;
int i;
getmax_substr(str, &pos, &max_sub_len);
printf("str is:%s\npos is %d, max_sub_len is %d\n",str,pos,max_sub_len);
for(i=0;i<max_sub_len;i++)
printf("%c",str[i+pos-1]);
printf("\n");
system("PAUSE");
return 0;
}
|
阅读(659) | 评论(0) | 转发(0) |
