当前位置： 首页 > 网站开发 > 正文

KMP算法应用(一)

网站开发 407 人阅读 抢沙发  
关键字:
1 星2 星3 星4 星5 星 (暂无评分)
Loading ... Loading ...
baidu_share

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

给定一个字符串，问最多是多少个相同子串不重叠连接构成。

KMP的next数组应用。这里主要是如何判断是否有这样的子串，和子串的个数。

若为abababa，显然除其本身外，没有子串满足条件。而分析其next数组，next[7] = 5，next[5] = 3，next[3] = 1，即str[2..7]可由ba子串连接构成，那怎么否定这样的情况呢？很简单，若该子串满足条件，则len%sublen必为0。sunlen可由上面的分析得到为len-next[len]。

因为子串是首尾相接，len/sublen即为substr的个数。

若L%(L-next[L])==0,n = L/(L-next[L]),else n = 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

#include<iostream>  
#include<cstdio>  
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] )     //pattern[i]表示后缀的单个字符，pattern[j]表示前缀的单个字符  
        {  
            ++i;  
            ++j;  
            if(pattern[i] != pattern[j])  
                next[i]=j;  
            else  
                next[i]=next[j];  
        }  
        else  
            j=next[j];    //若j值不相同，则j值回溯  
    }  
}//get_nextval  
 
int main(void)  
{  
    int len;  
    while(scanf("%s",pattern)!=EOF)  
    {  
        if(pattern[0]=='.')  
            break;  
        len=strlen(pattern);  
 
        get_nextval(pattern);             
 
        if(len%(len-next[len])==0)  
            printf("%d\n",len/(len-next[len]));  
        else  
            printf("1\n");  
 
    }  
    return 0;  
}

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

【上一篇】
【下一篇】

您可能还会对这些文章感兴趣！

KMP算法应用(一)：等您坐沙发呢！

发表评论