KMP

题目描述

给出两个字符串 s1​ 和 s2​，若 s1​ 的区间 [l,r] 子串与 s2​ 完全相同，则称 s2​ 在 s1​ 中出现了，其出现位置为 l。
现在请你求出 s2​ 在 s1​ 中所有出现的位置。

定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。
对于 s2​，你还需要求出对于其每个前缀 s′ 的最长 border t′ 的长度。

输入格式

第一行为一个字符串，即为 s1​。
第二行为一个字符串，即为 s2​。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 s2​ 在 s1​ 中出现的位置。
最后一行输出 ∣s2​∣ 个整数，第 i 个整数表示 s2​ 的长度为 i 的前缀的最长 border 长度。

输入输出样例

输入 #1复制

ABABABC
ABA

输出 #1复制

1
3
0 0 1 

说明/提示

样例 1 解释

对于 s2​ 长度为 3 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 1。

数据规模与约定

本题采用多测试点捆绑测试，共有 4 个子任务。

• Subtask 0（30 points）：∣s1​∣≤15，∣s2​∣≤5。
• Subtask 1（40 points）：∣s1​∣≤104，∣s2​∣≤102。
• Subtask 2（30 points）：无特殊约定。
• Subtask 3（0 points）：Hack。

对于全部的测试点，保证 1≤∣s1​∣,∣s2​∣≤106，s1​,s2​ 中均只含大写英文字母。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class Main {
	static int N=2*1000010;
	
   
    static int next[]=new int[N];
   

   public static void main(String[] args) throws IOException {
	 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	 BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	 

	 String s1=br.readLine();
	 String s2=br.readLine();
	 
	 //KMP算法
	 char s[]=(s2+"#"+s1).toCharArray();
	 
	 for (int i = 1,j=0; i < s.length; i++) {
		while(j>0 && s[i]!=s[j]){
			j=next[j-1];
		}
		
		if(s[i]==s[j]){
			next[i]=++j;
		}else{
			next[i]=j;
		}
		
	 }
	 
	 for (int i = 1; i < s.length; i++) {
		if(next[i]==s2.length()){
			int n=s2.length();
			bw.write((i-2*n+1)+"\n");
		}
	 }
	
	 
	 
	 for (int i = 0; i < s2.length(); i++) {
		bw.write(next[i]+" ");
	 }
	 
			 
	
	 
	 br.close();
	 bw.flush();
	 bw.close();
	 
   }
   
   
}

KMP找周期

题目描述

原题来自：BalticOI 2009

给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行给出字符串的长度 L，第二行给出一个字符串，全由小写字母组成。

输出格式

输出最短的长度。

样例

输入

8
cabcabca

输出

3

对于样例，我们可以利用 abc 不断自我连接得到 abcabcabc，读入的 cabcabca 是它的子串。

数据范围与提示

对于全部数据，1\le L\le 10^6。

. 图解两种情况：border 有重叠 与 border 无重叠

情况一：border 有重叠（长度 > n/2）

以 S = "abcabcab" 为例（n = 8）：

text

索引: 0 1 2 3 4 5 6 7
字符: a b c a b c a b

它的最长 border 是 abcab（长度 5），即 next[7] = 5。

text

前缀 abcab ：[0..4]
后缀 abcab ：[3..7]
它们重叠的区域是 [3..4] = "ab"

此时周期 T=n−b=8−5=3T=n−b=8−5=3，即 "abc"。
验证：将 "abc" 不断重复得 abc abc abc a...，原串 abcabcab 是它的子串（前面补一个 a 或直接前 8 位匹配）。
为什么 border 重叠时也成立？因为后缀的前 bb 个字符与前缀相同，且后缀的起始位置是 n−bn−b，所以从 00 到 n−b−1n−b−1 这部分（即 TT）决定了整个循环节。

情况二：border 无重叠（长度 ≤ n/2）

以 S = "abcdab" 为例（n = 6）：

text

索引: 0 1 2 3 4 5
字符: a b c d a b

最长 border 是 "ab"（长度 2），即 next[5] = 2。

text

前缀 ab : [0..1]
后缀 ab : [4..5]
它们完全不重叠。

周期 T=6−2=4T=6−2=4，即 "abcd"。
验证："abcd" 重复 → abcdabcdabcd...，原串 abcdab 恰好是它的前 6 位，完美匹配。
这时的 border 没有重叠，但依然满足：前缀 ab 与后缀 ab 相同，所以可以把字符串看作 abcd + ab，而 ab 正是 abcd 的前两个字符，自然能接上。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class Main {
	static int N=2*1000010;
	
   
    static int next[]=new int[N];
   

   public static void main(String[] args) throws IOException {
	 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	 BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	 
//	 StringTokenizer st=new StringTokenizer(br.readLine());
// 
	 int n=Integer.parseInt(br.readLine());
//	 int m=Integer.parseInt(st.nextToken());

	 char s[]=(br.readLine()).toCharArray();
	 
	 for (int i = 1,j=0; i < n; i++) {
		while(j>0 && s[i]!=s[j]){
			j=next[j-1];
		}
		if(s[i]==s[j]){
			next[i]=++j;
		}else{
			next[i]=j;
		}
	 }
//	 for (int i = 1; i < n; i++) {
//		System.out.println(next[i]+" ");
//	}
	 bw.write((n-next[n-1])+"");
	
	 
	 br.close();
	 bw.flush();
	 bw.close();
	 
   }
   
   
}