POJ 2752(Next数组的应用)

た入场券 2022-05-19 07:08 196阅读 0赞

[传送门][Link 1]

题意：给你一个字符串，要求你从小到大输出所有字符串中满足既是该字符串的前缀又是该字符串的后缀的子串的长度。

比如： "alala"的前缀分别为\{"a", "al", "ala", "alal", "alala"\}，后缀分别为\{"a", "la", "ala", "lala", "alala"\}。其中\{"a", "ala", "alala"\}是相同的，所以输出1，3，5。

分析：首先一个串它本身既是它自己的前缀又是它自己的后缀。根据Next数组，其实我们很容易发现Next数组存的就是一个字符串的前缀和后缀的最大匹配长度，Next\[len\]就是整个字符串的前后缀的最大匹配长度。

如左图，![format_png][]我们假设黑色线就是整个字符串str，长度为len，假定红线的长度代表Next\[len\]，根据Next数组定义我们知道前缀的Next\[len\]长度的子串和后缀Next\[len\]长度的子串完全相同（也就是两条红线所在的位置）。我们再求出Next\[len\]位置处的Next值(此时的len是截止到第二条蓝色部分的长度)，然后得到图中蓝线对应的长度。可以得到两个蓝线对应的子串肯定完全相同，因为第二条蓝线是左边那条红线的后缀，而左边那条红线其实是和右边那条红线相匹配的，所以可以肯定第二条蓝线肯定也是整个字符串的后缀，所以我们根据Next数组的值不断地往回跳，最后从小到大输出就行了。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 4e5+7;
    char s[maxn];
    int Next[maxn];
    int len,flag;
    
    void getNext()
    {
        int j = -1, i = 0;
        Next[0] = -1;
        while(i<len)
        {
            if(j==-1||s[i]==s[j])
            {
                i++;
                j++;
                Next[i]=j;
            }
            else j = Next[j];
        }
    }
    
    void dfs(int x)
    {
        if(x==0) return;
        dfs(Next[x]);
        if(flag==1){
            printf("%d",x);
            flag = 0;
        }else{
            printf(" %d",x);
        }
    }
    
    int main()
    {
        while(scanf("%s",s)!=EOF)
        {
            len = strlen(s);
            getNext();
            flag=1;
            dfs(len);
            cout<<endl;
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=2752
[format_png]: /images/20220519/89e1c4933d2d4b948abe39e66f7335b5.png