题解 P4391 【[BOI2009]Radio Transmission 无线传输】

Caicz · 2020-01-14 10:42:21 · 题解

刚学完KMP不到1小时就来做这道题，本题对next数组的理解和运用很巧妙

• 刚一做题，第一思路是先求出整条串的next值，然后从小到大枚举*for(i=2;i<=n;i+=2) 当i=2 next[i]时，输出此时的next值**

  但是该思路对以下两种情况无法处理

  1. 给定字符串为单个字符时 例： 1 a 此时的next数组全为0无法解决

  2. 还是直接举例: 8 aabaabaa 此时若用以上算法，会将最小循环子串误判长度为 1

• 所以，我们就得从next数组中找规律
• 设最小循环子串长度为 x，那么可以得到next[x]==0;

  证明：

  如果next[x]==len（0<len<x）,那么就有s[len]==s[x];

  那么去掉s[x]后得到的[1,x-1]依旧是原串的循环子串，因为 x 为最短长度，所以可得 next[x]一定为0;

  证毕；

• 所以我们可以推论得到next[x+1]==1; next[x+2]==2...
• 最终得到 nxet[n]==n-x

所以最终我们的答案即为 n-next[n]

代码：

#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
int n,len,next[1000005];
char s[1000005];

int main()
{
    scanf("%d %s",&n,s+1);
    int t1=0,t2;
    next[0]=t2=-1;
    while(t1<=n)
    {
        if(t2==-1||s[t2+1]==s[t1+1])
            next[++t1]=++t2;
        else
            t2=next[t2];
    }
    printf("%d",n-next[n]);
    return 0;
}