poj2752

不念不忘少年蓝@ 2021-10-30 01:36 141阅读 0赞

poj2752  
找所有的前缀等于后缀，那就是找所有前缀等于后缀的前缀，递归再用栈存一下

#include<iostream>
    #include<cstdio>
    #include<queue>
    #include<algorithm>
    #include<cmath>
    #include<ctime>
    #include<set>
    #include<map>
    #include<stack>
    #include<cstring>
    #define inf 2147483647
    #define ls rt<<1
    #define rs rt<<1|1
    #define lson ls,nl,mid,l,r
    #define rson rs,mid+1,nr,l,r
    #define N 400010
    #define For(i,a,b) for(int i=a;i<=b;i++)
    #define p(a) putchar(a)
    #define g() getchar()
    
    using namespace std;
    int kmp[N];
    int lb,k;
    char b[N];
    stack<int>s;
    void in(int &x){
        int y=1;
        char c=g();x=0;
        while(c<'0'||c>'9'){
            if(c=='-')y=-1;
            c=g();
        }
        while(c<='9'&&c>='0'){
            x=(x<<1)+(x<<3)+c-'0';c=g();
        }
        x*=y;
    }
    void o(int x){
        if(x<0){
            p('-');
            x=-x;
        }
        if(x>9)o(x/10);
        p(x%10+'0');
    }
    
    void clear(){
        k=0;
        memset(kmp,0,sizeof(kmp));
    }
    
    int main(){
        while(cin>>(b+1)){
            clear();
            lb=strlen(b+1);
            For(i,2,lb){
                while(k&&b[i]!=b[k+1])
                    k=kmp[k];
                if(b[k+1]==b[i])
                    k++;
                kmp[i]=k;
            }
            k=lb;
            s.push(lb);
            while(kmp[k]>0){
                s.push(kmp[k]);
                k=kmp[k];
            }
            while(!s.empty()){
                o(s.top());p(' ');
                s.pop();
            }
            p('\n');
        }
        return 0;
    }

转载于:https://www.cnblogs.com/war1111/p/11166061.html

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 25 阅读

相关 poj2752

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

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

相关 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 赞/ 126 阅读

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

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

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

相关 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 赞/ 131 阅读

相关 POJ 2752(Next数组的应用)

[传送门][Link 1] 题意：给你一个字符串，要求你从小到大输出所有字符串中满足既是该字符串的前缀又是该字符串的后缀的子串的长度。比如： "alala"的前缀分别为\

た入场券/ 2022年05月19日 07:08/ 0 赞/ 195 阅读

相关 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 赞/ 169 阅读

相关 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 赞/ 160 阅读

相关 kmp2-HDU1358 HUST1010 POJ2406 POJ2752

HDU1358 [http://acm.hdu.edu.cn/showproblem.php?pid=1358][http_acm.hdu.edu.cn_showprob

Dear 丶/ 2022年05月14日 11:25/ 0 赞/ 163 阅读

相关 poj2752

poj2752 找所有的前缀等于后缀，那就是找所有前缀等于后缀的前缀，递归再用栈存一下 include<iostream> include<cstdio>

不念不忘少年蓝@/ 2021年10月30日 01:36/ 0 赞/ 142 阅读