1),输出符合条件的前缀长度及其对应的n。" />
当前位置: 首页 > 网站开发 > 正文

KMP算法应用(二)

1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
1),输出符合条件的前缀长度及其对应的n。 ">
Loading ... Loading ...
baidu_share

http://poj.org/problem?id=1961

大意:
定义字符串A,若A最多由n个相同字串s连接而成,则A=s^n,如”aaa” = “a”^3,”abab” = “ab”^2
“ababa” = “ababa”^1

给出一个字符串A,求该字符串的所有前缀中有多少个前缀SA= s^n(n>1)
输出符合条件的前缀长度及其对应的n

如aaa
前缀aa的长度为2,由2个’a'组成
前缀aaa的长度为3,由3个”a”组成

分析:KMP
若某一长度L的前缀符合上诉条件,则
1.next[L]!=0(next[L]=0时字串为原串,不符合条件)

2.L%(L-next[L])==0(此时字串的长度为L/next[L])

对于2:有str[0]….str[next[L]-1]=str[L-next[L]-1]…str[L-1]
=》str[L-next[L]-1] = str[L-next[L]-1+L-next[L]-1] = str[2*(L-next[L]-1)];
假设S = L-next[L]-1;则有str[0]=str[s]=str[2*s]=str[3*s]…str[k*s],对于所有i%s==0,均有s[i]=s[0]
同理,str[1]=str[s+1]=str[2*s+1]….
str[j]=str[s+j]=str[2*s+j]….
综上,若L%S==0,则可得L为str[0]…str[s-1]的相同字串组成,
总长度为L,其中字串长度SL = s-0+1=L-next[L],循环次数为L/SL
故对于所有大于1的前缀,只要其符合上述条件,即为答案之一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>  
#include<cstdio>  
#include<cstring>  
using namespace std;  
 
char pattern[1000002];  
int next[1000002];  
 
/* 
kmp算法,需要首先求出模式串的next函数值 
next[j] = k,说明 p0pk-1 == pj-kpj-1,也就是说k为其前面相等串的长度 
*/  
void get_nextval(const char* pattern)  
{  
    int i=0,j=-1;  
    next[0]= -1;  
    while(pattern[i] != '\0')  
    {  
        if(j== -1 || pattern[i]== pattern[j] )  
        {  
            ++i;  
            ++j;  
            next[i]=j;  
        }  
        else  
            j=next[j];  
    }  
}//get_nextval  
 
int main(void)  
{  
    int i,len,n,j=1;  
    while(scanf("%d",&n)!=EOF)  
    {  
        if(!n)  
            break;  
        scanf("%s",pattern);  
        len=strlen(pattern);  
 
        get_nextval(pattern);  
 
        printf("Test case #%d\n",j++);  
        for(i=2;i<=len;i++)  
        {  
            if(i%(i-next[i])==0 && i/(i-next[i])>1)  
                printf("%d %d\n",i,i/(i-next[i]));  
        }  
        printf("\n");  
 
    }  
    return 0;  
}

本文固定链接: http://www.chepoo.com/kmp-apply-2.html | IT技术精华网

【上一篇】
【下一篇】

KMP算法应用(二):等您坐沙发呢!

发表评论