POJ - 2752 Seek the Name, Seek the Fame(KMP)

淡淡的烟草味﹌ 2022-06-05 08:51 112阅读 0赞

[点我看题][Link 1]

题意：找出字符串S前后缀相同的串的长度，升序输出。

分析：简单KMP，emmm很激动自己想出来了，虽然简单，不多说考虑前后缀相同的字符串对应字符是相同的。

//但是用set存答案T了，直接用数组就A了。

参考代码：

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<set>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    const int maxn = 1e6+10;
    int n;
    char S[maxn];
    int nxt[maxn];
    int ans[maxn];
    
    void GetNext()
    {
        int i = 0, j = -1;
        nxt[0] = -1;
        while( i < n)
        {
            if( j == -1 || S[i] == S[j])
                nxt[++i] = ++j;
            else
                j = nxt[j];
        }
    }
    
    int main()
    {
        while( ~scanf("%s",S))
        {
            n = strlen(S);
            GetNext();
            // for( int i = 0; i <= n; i++)
            //     printf("%d ",nxt[i]);
            // puts("");
    
            int p = nxt[n];
            int len = 0;
            while( p)
            {
                ans[len++] = p;
                p = nxt[p];
            }
            for( int i = len-1; i >= 0; i--)
                printf("%d ",ans[i]);
            printf("%d\n",n);
    
            // for( set<int> :: iterator it = ans.begin(); it != ans.end(); it++)
            //     printf("%d ",*it);
            // printf("%d\n",n);
        }
    
        return 0;
    }

[Link 1]: http://poj.org/problem?id=2752

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关 MTK6771 SEEK state

do Contrast AF search 做CAF搜索 Check if it needs to change direction 检查它是否需要改变方向 Check

亦凉/ 2022年09月10日 07:27/ 0 赞/ 164 阅读

相关 poj 2752 Seek the Name, Seek the Fame【kmp】

Seek the Name, Seek the Fame Description The little cat is so famous, that many couple

╰半橙微兮°/ 2022年08月21日 01:28/ 0 赞/ 17 阅读

相关 poj2752

Seek the Name, Seek the Fame <table> <tbody> <tr> <td><strong>Ti

r囧r小猫/ 2022年08月03日 13:39/ 0 赞/ 128 阅读

相关 POJ 2752 Seek the Name, Seek the Fame（KMP+next数组的运用）

The little cat is so famous, that many couples tramp over hill and dale to Byteland, and

拼搏现实的明天。/ 2022年06月10日 14:08/ 0 赞/ 121 阅读

相关【kmp算法next数组求解公共前后缀】Seek the Name, Seek the Fame POJ - 2752

Think: 1知识点：通过kmp算法next数组求解公共前后缀 2题意：输入串s，输出所有的符合条件的子串的长度，符合条件：子串既是s的前缀又是s的后缀 3解题知

爱被打了一巴掌/ 2022年06月07日 02:25/ 0 赞/ 140 阅读

相关 POJ - 2752 Seek the Name, Seek the Fame(KMP)

[点我看题][Link 1] 题意：找出字符串S前后缀相同的串的长度，升序输出。分析：简单KMP，emmm很激动自己想出来了，虽然简单，不多说考虑前后缀相同的字符串对应字

淡淡的烟草味﹌/ 2022年06月05日 08:51/ 0 赞/ 113 阅读

相关 POJ - 2752 Seek the Name, Seek the Fame (KMP)

Seek the Name, Seek the Fame Description The little cat

阳光穿透心脏的1/2处/ 2022年05月19日 08:57/ 0 赞/ 127 阅读

相关 KMP-(POJ 2752)Seek the Name, Seek the Fame

KMP-(POJ 2752)Seek the Name, Seek the Fame -------------------- 题目链接：[11:Seek

缺乏、安全感/ 2022年05月17日 01:18/ 0 赞/ 164 阅读

相关 POJ 2752 Seek the Name, Seek the Fame——————KMP next 数组的运用

Seek the Name, Seek the Fame Language:Default Seek the Name, Seek the Fame <table>

迈不过友情╰/ 2022年05月16日 09:27/ 0 赞/ 153 阅读

相关 O - Seek the Name, Seek the Fame

题目描述： The little cat is so famous, that many couples tramp over hill and dale to Byte

悠悠/ 2022年03月21日 13:28/ 0 赞/ 154 阅读