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

KMP算法应用(三)

1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

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

大意:
给出一个字符串A,求A有多少个前缀同时也是后缀,从小到大输出这些前缀的长度。

分析:KMP
对于长度为len的字符串,由next的定义知:
A[0]A[1]…A[next[len]-1]=A[len-next[len]]…A[len-1]此时A[0]A[1]…A[next[len]-1]为一个符合条件的前缀
有A[0]A[1]….A[next[next[len]]-1] = A[len-next[next[len] – next[next[len]]]…A[next[len]-1],故A[0]A[1]….A[next[next[len]]-1]也是一个符合条件的前缀

故从len=>next[len]=>next[next[len]] ….=>直到某个next[]为0均为合法答案,注意当首位单词相同时,也为答案。

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
53
54
55
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<vector>  
using namespace std;  
 
char pattern[400002];  
int next[400002];  
 
/* 
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;  
    vector<int>ans;  
    while(scanf("%s",pattern)!=EOF)  
    {  
        ans.clear();  
        len=strlen(pattern);  
        get_nextval(pattern);  
        n=len;  
        while(n)  
        {  
            ans.push_back(n);  
            n=next[n];  
        }  
        if(pattern[0]==pattern[n-1])   //首部、尾部字符相同  
            ans.push_back(1);  
 
        i=ans.size()-1;  
        for(;i>0;i--)  
            printf("%d ",ans[i]);  
        printf("%d\n",ans[0]);  
    }  
    return 0;  
}

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

【上一篇】
【下一篇】

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

发表评论