基础算法题——Radio Transmission（KMP-next 妙用）

比眉伴天荒 2022-12-20 02:06 160阅读 0赞

#### [Radio Transmission][] ####

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]

#### 解题思路 ####

在KMP算法中 next\[l\] 记录的就是字符串最长的相同的前缀与后缀，也就是说在题目字符串中有一段字符串是重复出现的，那么减去重复出现的字符串以后，剩下的就是这个字符串最小的循环节。

比较字符串的 next 数组

![运行结果][20201109193550521.png_pic_center]  
s1 的循环节：abc 或 bca、cab  
s2 的循环节：abcd 或 bcda、cdab、dabc  
结果符合预期

--------------------

实现代码

#include<bits/stdc++.h>
    using namespace std;
    int next[1000010];
    string s;
    
    void get_next(){ 
    	int j=-1, i=0;
    	next[0]=-1;
    	while(i<s.size()){ 
    		if(j==-1||s[j]==s[i]){ 
    			j++;
    			i++;
    			next[i] = j;
    		}
    		else
    			j = next[j];
    	}
    	return ; 
    }
    
    int main(){ 
    	int n;
    	scanf("%d", &n);
    	cin>>s;
    	get_next();
    /* printf(" %c ", s[0]); for(int i=1; i<=s.size(); i++) printf("%c ", s[i]); printf("\n"); for(int i=0; i<=s.size(); i++) printf("%d ", next[i]); printf("\n");*/
    	printf("%d", n-next[n]);
    	return 0;
    }

[Radio Transmission]: https://loj.ac/problem/10045
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/6d71950fbf8146ae87f6ce83e0c3aeba.png
[20201109193550521.png_pic_center]: /images/20221120/c6a67b651c494593a0d2d48624286ccc.png