KMP--多道列題+知識點

1.算法介紹

KMP是經典得不能再經典的字元串查找算法。它用來對字元串查找時的時間複雜度的優化，通過預處理減少大部分沒必要計算的問題。

2.算法正題

比如

A：aaabsaabssb lena=11;

B：bssb lenb=4;

以下數組下标從1開始

（1）.一般暴力方法：

我們一個一個查找。先聲明兩個指針變量i，j。

如果A[i+1]==B[j+1]，就i++，j++；

如果不是，就j=1，i=i-lenb+1；

這段代碼的意思就是，我們一個一個枚舉母串的起點。

顯然這樣的算法是十分費時的，我們就可以通過KMP來減少處理的次數。

（2）正題：KMP

1.思想：

在我們發現A[i+1]!=B[j+1]時，我們的暴力算法是需要我們再從頭到尾掃一遍。很明顯不用這樣就浪費了我們前面做出的努力。

易得：我們的求解b[1…j]要跟我們的A[i-j+1…i]完全相等。當A[i+1]!=B[j+1]，我們就需要對j做出改變。那麼問題來了，我們的j變為多少呢？goodquestion。這就是KMP的核心了。

舉例：比如B：acbacaba A：acbacbacbacaba

當j=5，i=5；A[i+1]!=B[j+1]；我們就可以将j變為2而不是0；

這樣就會減少j變為1的更多運算。

很顯然：我們得到的j’，就是一個該字元串的最大相等字首和字尾

比如： abab ：j’=2 abbbcdabbbc ：j’=5

我們直接預處理出一個j’數組，在程式運作直接獲得就好。

2.預處理數組實作（這是一個在KMP中很重要的點）：

求p[j’]數組：表示沒能夠比對，j将要變成的值

原理：

B :ababacd

已經知道p[1-4] ,我們來尋找一下p[5],p[6];

p[1]=0;

p[2]=0;

p[3]=1;

p[4]=2;

因為p[4]=2&&B[3]=B[5]

是以p[5]=p[4]+1;

p[6]?

貌似很棘手啊

我們來想一下p數組的性質，它是用來存儲最大相等字首和字尾的。

求解p[j]我們應該周遊已經找到的p[j’],

根據p[5]=p[4]+1,很多人會想，p[j]=p[j’]+1 &&j’=j-1?這個等式的成立是有條件的，即B[p[j’]]=B[j]

比如 abcabc 如果要達到p[6]=p[5]+1,就需要達到B[6]=B[3].

想到這裡問題就比較明朗了，比如找p[6],如果p[5]不能取，那麼我們就找p[p[5]].一直找到1為止

void pre()
{
	p[1]=0;
	int j=0;
	for(int i=1;i<len2;i++)
	{
		while(j>=1&&b[i+1]!=b[j+1]) j=p[j];
		if(b[i+1]==b[j+1]) j++;//能夠比對了，我們就加上已經比對好的B[i+1]
		p[i+1]=j;	
	}
}
           

3.KMP内容

有了神器P數組的幫助，我們求解内容其實就跟暴力差不多了，隻是在改變j的時候改為P[j]就好。

void kmp()
{
	int j=0;
	for(int i=0;i<len1;i++)
	{
		while(j>=1&&a[i+1]!=b[j+1]) j=p[j];//不能比對，再次尋找
		if(a[i+1]==b[j+1]) j++;
		if(j==len2)
		{
			cout<<i-j+2<<endl;
			j=p[j];//繼續尋找比對的
		}
	}
}
           

可以發現的是，這一段代碼和上一段代碼相似度很高。因為它們兩個都是一個尋找比對的過程，是以大緻相同的

3.例題詳解

（1）P3375模闆題

傳送門

題目描述

如題，給出兩個字元串s1和s2，其中s2為s1的子串，求出s2在s1中所有出現的位置。

為了減少騙分的情況，接下來還要輸出子串的字首數組next。

（如果你不知道這是什麼意思也不要問，去百度搜[kmp算法]學習一下就知道了。）

輸入格式

第一行為一個字元串，即為s1

第二行為一個字元串，即為s2

輸出格式

若幹行，每行包含一個整數，表示s2在s1中出現的位置

接下來1行，包括length(s2)個整數，表示字首數組next[i]的值。

輸入輸出樣例

輸入 #1 複制

ABABABC

ABA

輸出 #1 複制

1

3

0 0 1

說明/提示

時空限制：1000ms,128M

資料規模：

設s1長度為N，s2長度為M

對于30%的資料：N<=15，M<=5

對于70%的資料：N<=10000，M<=100

對于100%的資料：N<=1000000，M<=1000000

樣例說明：

是以兩個比對位置為1和3，輸出1、3

題解

這是一道很基礎的模闆題，直接上模闆就可以了

附上AC代碼+注釋

#include<bits/stdc++.h>
#define maxn 1000050
using namespace std;
char a[maxn];
char b[maxn];
int p[maxn];
int len1,len2;
void pre()
{
	p[1]=0;
	int j=0;
	for(int i=1;i<len2;i++)
	{
		while(b[j+1]!=b[i+1]&&j>0) j=p[j];
		if(b[i+1]==b[j+1])	j++;
		p[i+1]=j;
	}
}
void kmp()
{
	int j=0;
	for(int i=0;i<len1;i++)
	{
		while(j>0&&b[j+1]!=a[i+1]) j=p[j];
		if(a[i+1]==b[j+1]) j++;
		if(j==len2)
		{
			cout<<i-j+2<<endl;
			j=p[j];
		}
	}
}
int main()
{
	cin>>a+1;	//表示字元串首部是a[1]
	scanf("%s",b+1);
	len1=strlen(a+1);
	len2=strlen(b+1);	
	pre();
	kmp();
	for(int i=1;i<=len2;i++)
	cout<<p[i]<<" ";
	cout<<endl;
	return 0;
}
           

（2）P4391

傳送門

題目描述

給你一個字元串，它是由某個字元串不斷自我連接配接形成的。 但是這個字元串是不确定的，現在隻想知道它的最短長度是多少.

輸入格式

第一行給出字元串的長度,1 < L ≤ 1,000,000.

第二行給出一個字元串，全由小寫字母組成.

輸出格式

輸出最短的長度

輸入輸出樣例

輸入 #1 複制

8

cabcabca

輸出 #1 複制

3

說明/提示

對于樣例,我們可以利用"abc"不斷自我連接配接得到"abcabcabc",讀入的cabcabca,是它的子串

個人意見：将“abc”改成“cab”

題解

1.分析

此題做法還是有一點投機的。有關子母字元串，很容易讓人想到KMP算法，此題也正是使用這種方法。

p[]:定義字元串b的最大相等字首和字尾。

x:求解目标，最小子串

分析一下樣例，很明顯 ：p[x]=0；

p[x+1]=x+1-x=1;

p[n]=n-x;

是以我們就可以根據這個很容易地求到n-p[n]=x;

2.附上AC代碼+注釋

#include<bits/stdc++.h>
#define maxn 1000050
using namespace std;
char b[maxn];
int p[maxn];
int len;
void pre()
{
	int j=0;
	p[1]=0;
	for(int i=1;i<len;i++)
	{
		while(j>=1&&b[i+1]!=b[j+1]) j=p[j];
		if(b[i+1]==b[j+1]) j++;
		p[i+1]=j;
	}
}
int main()
{
	cin>>len;
	cin>>b+1;//字元串首為b[1];
	pre();//計算p
	cout<<len-p[len];
	return 0;
} 
           

（3）

P3435 [POI2006]OKR-Periods of Words

傳送門

題目描述

A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of 0 letters. By A=BC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings B and C (in this order). A string P is a prefix of the string !, if there is a string B, that A=PB. In other words, prefixes of A are the initial fragments of A. In addition, if P!=A and P is not an empty string, we say, that P is a proper prefix of A.

A string Q is a period of Q, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn’t have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.

Task Write a programme that:

reads from the standard input the string’s length and the string itself,calculates the sum of lengths of maximum periods of all its prefixes,writes the result to the standard output.

一個串是有限個小寫字元的序列,特别的,一個空序列也可以是一個串. 一個串P是串A的字首, 當且僅當存在串B, 使得 A = PB. 如果 P A 并且 P 不是一個空串,那麼我們說 P 是A的一個proper字首. 定義Q 是A的周期, 當且僅當Q是A的一個proper 字首并且A是QQ的字首(不一定要是proper字首). 比如串 abab 和 ababab 都是串abababa的周期. 串A的最大周期就是它最長的一個周期或者是一個空串(當A沒有周期的時候), 比如說, ababab的最大周期是abab. 串abc的最大周期是空串. 給出一個串,求出它所有字首的最大周期長度之和.。

輸入格式

In the first line of the standard input there is one integer kk (1\le k\le 1\ 000\ 0001≤k≤1 000 000) - the length of the string. In the following line a sequence of exactly kk lower-case letters of the English alphabet is written - the string.

輸出格式

In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.

輸入輸出樣例

輸入 #1 複制

8

babababa

輸出 #1 複制

24

題解

1.分析

先翻譯一下這道讓人無法看懂的題。

給出一個數組，長度為n。

你需要對它的n個字首進行操作

操作：比如現在我們需要操作字首i。你需要找出該i字元串的最大周期。并且把n個字首的最大周期的值加起來。

既然需要加上最大周期，那麼怎麼求最大周期呢？

如圖，每個字元串都可以分為三個小字元串，我們稱為1,2,3号；（從左往右的順序）

當1号3号完全相等時，1和2，或者2和3就構成了一個周期；

最大：也就是1和3越小時周期T就會越大

根據前後相等的性質（1号和3号），我們很自然就想到了KMP中的next數組（我習慣用p數組來表示）。那麼怎麼求最小呢，我們一直遞歸下去就好了

放一段僞代碼吧；

ll print()
{
	for(int i=1;i<=n;i++)
	{
		int j=i;
		while(next[j]) j=next[j];
		ans+=i-j;
		if(next[i]) next[i]=j;
		 //這裡是一個優化，相當于以後我在通路next[i]，可以一步到位，有點像并查集的優化
		 //如果這裡不優化的化應該會有60分
	}
	return ans;
}
           

2.附上AC代碼+注釋

#include<bits/stdc++.h>
#define maxn 1000005
#define ll long long int 
using namespace std;
int n;
char a[maxn];
int next[maxn];
void pre()
{
	next[1]=0;
	int j=0;
	for(int i=1;i<n;i++)
	{
		while(j>=1&&a[i+1]!=a[j+1]) j=next[j];
		if(a[i+1]==a[j+1]) j++;
		next[i+1]=j;
	}
}
ll ans=0;
ll print()
{
	for(int i=1;i<=n;i++)
	{
		int j=i;
		while(next[j]) j=next[j];
		ans+=i-j;
		if(next[i]) next[i]=j; 
	}
	return ans;
}
int main()
{
	cin>>n;
	cin>>a+1;//數組首項從a[1]開始
	pre();
	cout<<print();
	return 0;
}