题解

47 条题解

  • 3
    @ 2017-09-09 15:07:46

    思路很巧,看了楼下题解才知道怎么做orz

    #include<iostream>
    #include<algorithm>
    #include<cstdio> 
    #include<cstring>
    #include<vector>
    using namespace std;
    
    int nxt[1000010];                      //写成next在这里会CE qwq
    string s;
    int n;
    
    void find_next(){                      //处理nxt数组(最长前缀=后缀);递推的思想
         for(int i=2;i<=n;i++){
                 int k=nxt[i-1];
                 while(k&&s[i-1]!=s[k]) k=nxt[k];
                 if(s[k]==s[i-1]) nxt[i]=k+1;
         }
    }
    
    int main(){
        cin>>s;
        n=s.length();
        find_next();
        int t=n, ans=n;
        while(t&&nxt[t]) t--;           //找到第一个末位元素与首位不同的长度t
        while(nxt[ans]>=t) ans=nxt[ans];//可证ans肯定>=t;从中再找最短(后缀=前缀)的长度
        cout<<ans<<endl;
      return 0;
    }
    
  • 2
    @ 2016-08-12 10:26:52
    • 测试数据 #0: Accepted, time = 0 ms, mem = 10344 KiB, score = 10
    • 测试数据 #1: Accepted, time = 0 ms, mem = 10348 KiB, score = 10
    • 测试数据 #2: Accepted, time = 0 ms, mem = 10344 KiB, score = 10
    • 测试数据 #3: Accepted, time = 0 ms, mem = 10348 KiB, score = 10
    • 测试数据 #4: Accepted, time = 0 ms, mem = 10348 KiB, score = 10
    • 测试数据 #5: Accepted, time = 0 ms, mem = 10348 KiB, score = 10
    • 测试数据 #6: Accepted, time = 15 ms, mem = 10352 KiB, score = 10
    • 测试数据 #7: Accepted, time = 15 ms, mem = 10348 KiB, score = 10
    • 测试数据 #8: Accepted, time = 31 ms, mem = 10344 KiB, score = 10
    • 测试数据 #9: Accepted, time = 31 ms, mem = 10344 KiB, score = 10

    Accepted, time = 92 ms, mem = 10352 KiB, score = 100
    我表示不知道为什么A了。难道我想出了正解??
    思路是:
    首先考虑如何判断一个前缀是否能覆盖(感觉好像是):P[1..i]能覆盖P当且仅当对于任意一个k > i,有next[k] != 0 且 next[k] <= i 意思大概是后面每一个都能被当P[1..i]的某个前缀匹配【语言表达能力捉急】用数组预处理下O(n)可以做到O(1)询问
    由于开头和结尾不会被覆盖,next[n]是子串的最长值。且可以证(cai)明(chu):如果P[1..i]可以覆盖P,对于任意next[i] < k < i,P[1..k]不能覆盖P。【证(cai)明(xiang)过程自行脑补】
    预处理复杂度O(n),后面的计算也是O(n),不过后面的实际情况好得多。当所有字符相同是,可以到O(lgn)。平均一下应该不错
    ```c++
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;

    int nextq[1000005], n, m;
    int minn[1000005];
    char P[1000005], T[1000005];

    void kmp_init()
    {
    int k = 0;
    nextq[0] = nextq[1] = 0;
    for (int i = 2; i <= n; i++) {
    while (k && P[k+1] != P[i]) k = nextq[k];
    if (P[k+1] == P[i]) k++;
    nextq[i] = k;
    }
    }

    inline bool match(int i)
    {
    return minn[i+1] != 0 && minn[i+1] <= i;
    }

    int main
    {
    memset(minn, 127/3, sizeof minn);
    gets(P+1); n = strlen(P+1);
    kmp_init();
    minn[n] = nextq[n];
    for (int i = n-1; i; i--)
    minn[i] = min(nextq[i], minn[i+1]);
    int k = nextq[n], ans;
    if (!match(k)) {
    cout << n << endl;
    return 0;
    }
    while (k && match(k)) {
    ans = k;
    k = nextq[k];
    }
    cout << ans << endl;
    return 0;
    }

    • @ 2016-08-12 10:29:43

      可恶的是CE了一次,貌似不能用next当名字??

      foo.cpp: In function 'void kmp_init()':
      foo.cpp:13:9: error: reference to 'next' is ambiguous
      next[0] = next[1] = 0;

    • @ 2018-08-19 15:55:37

      @ljt12138: C++11标准库有一个std::next函数

  • 1
    @ 2016-11-17 15:07:47

    谢谢楼下题解!
    #include<bits/stdc++.h>
    #define MAXN 1010105
    using namespace std;
    char P[MAXN];
    int f[MAXN];
    void read(char* s)
    {
    char ch;int tot=0;
    ch=getchar();
    while(ch!='\n'){
    s[tot++]=ch;ch=getchar();
    }
    }
    int main()
    {
    read(P);int m=strlen(P);
    f[0]=f[1]=0;
    for(int i=1;i<m;i++){
    int j=f[i];
    while(j&&P[j]!=P[i])j=f[j];
    f[i+1]=(P[j]==P[i])?j+1:0;
    }
    int k,ans=m;
    for(int i=m;i>=0;i--){
    if(f[i]==0){k=i;break;}
    }
    while(f[ans]>=k)ans=f[ans];
    cout<<ans;
    }

  • 0
    @ 2018-08-19 17:22:37

    首先注意读题,“他从自己名字的开头截取了一段作为模板”,也就是说模式串一定在开头和结尾都完整地出现了一次(位置上可能有交集)。楼下不少人举的反例都不符合题目要求。

    我的解法用到了标准KMP和扩展KMP算法,标准KMP算法的next[i]表示子串str[0, i]中除去自身以外既是前缀又是后缀的最大长度,而扩展KMP算法的next[i]表示后缀str[i, N)str自身的最长公共前缀长度。下文中用kmp:next[i]exkmp:next[i]加以区分。

    假设前缀str[0, k)是符合要求的模式串,那么它应满足:
    (1)对于任意i >= ki < N,都有kmp:next[i] > 0
    (2)exkmp:next[N - k] == k,即模式串在开头和结尾都完整地出现了一次。

    答案就是符合上述两个条件的最小的k,算法复杂度为O(N)。

    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #define BEGIN_NAMESPACE(name) namespace name {
    #define END_NAMESPACE(name) }
    
    //标准KMP算法,数组下标从0开始
    //next[i]表示val[0..i]所有前缀与所有后缀的交集中,除本身外最大的长度
    BEGIN_NAMESPACE(kmp) 
    template <class Tp, int N>
    struct Pattern 
    {
        Tp  val[N]; int next[N]; int size;
        template <class RAIter>
        void init(RAIter first, RAIter last) //使用前必须调用初始化过程
        {
            std::copy(first, last, val); size = last - first;
            int v = -1, *np = next;
            for (RAIter cur = first; cur != last; ++cur, ++np) {
                while (v != -1 && *cur != first[v])
                    v = (v == 0 ? -1 : next[v - 1]);
                v = *np = v + 1;
            }
        }
    };
    END_NAMESPACE(kmp)
    
    //扩展KMP算法,数组下标从0开始
    //next[i]表示val[i..len)与val[0,len)的最长公共前缀的长度
    BEGIN_NAMESPACE(exkmp)
    template <class Tp, int N>
    struct Pattern
    {
        Tp val[N]; int next[N]; int size;
        template <class RAIter, class OIter>
        void calc_ext(RAIter first, RAIter last, OIter dest) //将extend数组输出到dest开头的位置
        {
            if (first == last)
                return;
            RAIter lp = first, rp = first;
            for (RAIter cur = first; cur != last; ++cur, ++dest) {
                if (cur + next[cur - lp] < rp)
                    *dest = next[cur - lp];
                else {
                    lp = cur; if (cur > rp) rp = cur;
                    for (; rp != last && *rp == val[rp - cur]; ++rp) {}
                    *dest = rp - cur;
                }
            }
        }
        template <class RAIter>
        void init(RAIter first, RAIter last) //使用前必须调用初始化过程
        {
            std::copy(first, last, val); next[0] = size = last - first;
            calc_ext(first + 1, last, next + 1);
        }
    };
    END_NAMESPACE(exkmp)
    
    const int maxN = (int)1e6 + 10;
    char str[maxN];
    int N;
    
    void input()
    {
        scanf("%s", str);
        N = strlen(str);
    }
    
    kmp::Pattern<char, maxN> pat;
    exkmp::Pattern<char, maxN> expat;
    
    int solve()
    {
        pat.init(str, str + N);
        expat.init(str, str + N);
        
        int ans = 1;
        for (int i = 1; i < N; i++)
            if (pat.next[i] == 0)
                ans = i + 1;
    
        while (ans < N && expat.next[N - ans] < ans) 
            ans += 1;
        
        return ans;
    }
    
    int main()
    {
        input();
        printf("%d\n", solve());
        return 0;
    }
    
  • 0
    @ 2016-06-27 15:15:50

    怎么感觉楼下的不适用于类似“ababcab” 和 "abcabcdabc"之类的字符串。。。

  • 0
    @ 2016-06-06 20:05:25

    不得不说,神奇的KMP……
    容易想到对于最大的i使得f[i]=0,用前i个覆盖可以把所有字符覆盖完整。
    不过考虑到覆盖的部分不可以超过整个名字(即覆盖完了以后不能多),应该沿f[len]走到第一个k使得f[k]<上述f[i],此k即为所求。
    ```c++
    #include<cstdio>
    #include<cstring>
    using namespace std;

    char input[1000100];
    int f[1000100],ans,n;

    int main()
    {
    memset(input,0,sizeof(input));
    memset(f,0,sizeof(input));
    scanf("%s",input);
    n=strlen(input);

    f[0]=f[1]=0;
    for(int i=1;i<n;i++)
    {
    int j=f[i];
    while( j && input[j]!=input[i] ) j=f[j];
    f[i+1]= input[j]==input[i] ? j+1 : 0;
    }

    int k;
    for(int i=n;i>=0;i--)
    if(f[i]==0) {k=i;break;}
    ans=n;
    while(f[ans]>=k) ans=f[ans];

    printf("%d\n",ans);
    return 0;
    }
    ```

    • @ 2016-10-10 01:11:46

      请尝试数据 abcabcabcdabcd

  • 0
    @ 2015-04-13 16:08:04

    #include<cstdio>
    #include<cstring>
    using namespace std;
    #define maxn 1000005
    int next[maxn],n;
    char s[maxn];
    /*
    处理出这个状态失配时的前一个状态所在位置
    如:abcab中
    next[i]=0表示下一个要匹配的是第一个a
    next[0]=0;(0表示第一个a)
    next[1]=0;next[2]=0;next[3]=0;next[4]=1;next[5]=2
    */
    void getnext()

    {
    next[0]=0;
    for(int i=1;i<n;i++){
    int j=next[i];
    while(j&&s[i]!=s[j]) j=next[j];
    next[i+1]=s[i]==s[j]?j+1:0;
    }
    }

    int main()

    {

    scanf("%s",&s);n=strlen(s);getnext();
    int T=n;
    int ans=n;
    while(next[T]!=0) T--; //从后删去一定能匹配的
    while(next[ans]>=T) ans=next[ans]; //找到第一个小于等于T的ans
    printf("%d",ans);

    }

    • @ 2016-05-03 15:20:06

      楼主,你的程序输入abbabbaa的时候会输出8诶
      但是abbaa长度5就可以啦 是不是你贪心的时候有点问题
      求正解

    • @ 2016-08-12 10:31:02

      回楼上,重新读题:“从名字开头选取”。请问您的例子中是从开头选的么??

  • 0
    @ 2015-04-13 16:07:23

    #include<cstdio>
    #include<cstring>
    using namespace std;
    #define maxn 1000005
    int next[maxn],n;
    char s[maxn];
    /*
    处理出这个状态失配时的前一个状态所在位置
    如:abcab中
    next[i]=0表示下一个要匹配的是第一个a
    next[0]=0;(0表示第一个a)
    next[1]=0;next[2]=0;next[3]=0;next[4]=1;next[5]=2
    */
    void getnext()

    {
    next[0]=0;
    for(int i=1;i<n;i++){
    int j=next[i];
    while(j&&s[i]!=s[j]) j=next[j];
    next[i+1]=s[i]==s[j]?j+1:0;
    }
    }
    int main()
    {
    scanf("%s",&s);n=strlen(s);getnext();
    int T=n;
    int ans=n;
    while(next[T]!=0) T--; //从后删去一定能匹配的
    while(next[ans]>=T) ans=next[ans]; //找到第一个小于等于T的ans
    printf("%d",ans);
    }

  • 0
    @ 2014-08-29 10:24:56

    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <cstdio>
    #include <vector>
    using namespace std;
    #define maxn 1100000
    int next[maxn],n;
    char st[maxn];
    void getnext()
    {
    next[0]=0;
    for(int i=1;i<n;i++)
    {
    int j=next[i];
    while(j&&st[i]!=st[j])
    {
    j=next[j];
    }
    if(st[i]==st[j])
    {
    next[i+1]=j+1;
    }
    else
    {
    next[i+1]=0;
    }
    }
    }
    int main()
    {
    scanf("%s",st);
    n=strlen(st);
    getnext();
    int T=n;
    int ans=n;
    while(next[T]!=0)
    {
    T--;
    }
    //printf("%d",T);

    while(next[ans]>=T)
    {
    ans=next[ans];
    }
    printf("%d",ans);

    return 0;
    }
    /*
    abcabcabca
    */

  • 0
    @ 2014-02-23 20:33:19

    这是哪里的题?求来历!

  • 0
    @ 2013-10-16 22:58:56

    记录信息
    评测状态 Wrong Answer
    题目 P1677 陶陶的名字
    递交时间 2013-10-16 22:55:05
    代码语言 C
    评测机 上海红茶馆
    消耗时间 779 ms
    消耗内存 540 KiB
    评测时间 2013-10-16 22:55:06

    评测结果
    编译成功

    测试数据 #0: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

    测试数据 #1: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

    测试数据 #2: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

    测试数据 #3: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

    测试数据 #4: Accepted, time = 0 ms, mem = 532 KiB, score = 10

    测试数据 #5: Accepted, time = 109 ms, mem = 540 KiB, score = 10

    测试数据 #6: WrongAnswer, time = 187 ms, mem = 536 KiB, score = 0

    测试数据 #7: WrongAnswer, time = 156 ms, mem = 536 KiB, score = 0

    测试数据 #8: WrongAnswer, time = 171 ms, mem = 540 KiB, score = 0

    测试数据 #9: WrongAnswer, time = 156 ms, mem = 532 KiB, score = 0

    WrongAnswer, time = 779 ms, mem = 540 KiB, score = 20

    代码
    #include <stdio.h>
    int main (){
    int i=0;
    char a;
    scanf ("%c",&a);
    while (a!='\n')
    {i++;
    scanf ("%c",&a);
    }
    printf ("%d\n",i);
    return 0;
    }

    PS:奇迹啊!

    • @ 2015-10-07 16:52:15

      hehehehehehe.................................................

  • 0
    @ 2012-10-15 15:10:06

    正确性就是说,这个东西肯定是个单增的找到最初的增点就好了

  • 0
    @ 2009-11-10 15:01:49

    赞,好数据!

  • 0
    @ 2009-11-10 15:01:30

    样例输入:

    Matt

    样例输出:

    4

    此时的模板为:沙茶

  • 0
    @ 2009-11-07 11:46:41

    扩展KMP……

    大家可以看看这个专题:

    http://www.oibh.org/bbs/attachment.php?aid=14357

    里面《扩展KMP算法》的第一个例题貌似就是这题

  • 0
    @ 2009-11-02 13:22:57

    比赛的时候写了个自我匹配。

    然后不知道接下来该如何处理就交上去了。

    评出来当时有40分觉得挺知足。

    结果回头发现后面都201错误。

    范围里少数了个0。。

    再改了下范围交。。就80分了。。本来就能有2个Q币花了啊。。

    怨念中。

  • 0
    @ 2009-11-02 00:43:28

    orz

  • 0
    @ 2009-11-01 23:00:50

    偶不明白那个KMP是什么意思,所以我没用那个方法。

    我弱弱地写了个暴力,就过了......

    暴力的方法:

    正着一遍扩展KMP,倒着一遍扩展KMP。二分答案,验证

    时间复杂度O(nlogn)

    中间出现了个小问题,就是5,6组数据的答案是数据长度。也就是说,不要忘了特判这种情况(如果你和我一样暴力的话)

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 9ms

    ├ 测试数据 07:答案正确... 25ms

    ├ 测试数据 08:答案正确... 25ms

    ├ 测试数据 09:答案正确... 41ms

    ├ 测试数据 10:答案正确... 72ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:172ms

  • 0
    @ 2009-11-01 10:08:42

    提示一下:模板完整必出现在字符串的末尾……

  • 0
    @ 2009-10-30 21:57:46

    用kmp来做,线性的复杂度。

    核心代码:

    begin

    init;

    work;

    end.

    有一个地方要注意,就是不能把名字多写。

    比如"abcab"答案应该是5而不是3。如果是3,就会变成"abcabc"是错的。

信息

ID
1677
难度
8
分类
字符串 | KMP 点击显示
标签
递交数
2296
已通过
212
通过率
9%
被复制
1
上传者