题解 - Vijos

3

eurus LV 8 @ 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

ljt12138 LV 10 @ 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;
}

ljt12138 @ 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;
Orina_zju @ 2018-08-19 15:55:37

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

1

蒋天奇 LV 8 @ 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

Orina_zju LV 8 @ 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 >= k且i < 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

everforever LV 10 @ 2016-06-27 15:15:50

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

0

qig159357 LV 8 @ 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;
}
```

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

请尝试数据 abcabcabcdabcd

0

xujingbin LV 7 @ 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就可以啦是不是你贪心的时候有点问题
求正解
ljt12138 @ 2016-08-12 10:31:02

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

0

xujingbin LV 7 @ 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

xujiahe LV 10 @ 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

一方T行 LV 10 @ 2014-02-23 20:33:19

这是哪里的题？求来历！

0

lemontree712 LV 10 @ 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

TodM LV 7 @ 2012-10-15 15:10:06

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

0

lulu93 LV 7 @ 2009-11-10 15:01:49

赞，好数据！

0

Matt LV 10 @ 2009-11-10 15:01:30

样例输入：

Matt

样例输出：

4

此时的模板为：沙茶

0

sixhomeland LV 9 @ 2009-11-07 11:46:41

扩展KMP……

大家可以看看这个专题：

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

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

0

Aries_C LV 9 @ 2009-11-02 13:22:57

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

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

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

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

范围里少数了个0。。

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

怨念中。

0

curimit LV 10 @ 2009-11-02 00:43:28

orz

0

ACcreator LV 9 @ 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

1s LV 10 @ 2009-11-01 10:08:42

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

0

ufo172849z LV 10 @ 2009-10-30 21:57:46

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

核心代码：

begin

init;

work;

end.

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

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

题解

47 条题解

陶陶的名字

信息

状态

开发

支持

题解

47 条题解

陶陶的名字

信息

状态

开发

支持

还没有账户？

登录