字元串系列——KMP、AC自動機、回文自動機

文章目錄

• KMP
• • code
  • 例題
  • • 題解
    • code
• AC自動機
• • code
  • 例題
  • • 題解
    • code
• 回文自動機
• • 例題
  • • 題解
    • code
  • 參考資料

個人感覺字元串系列是比較蛋疼的算法（相對于我來說）。。。

KMP

給出比對串和模式串，求模式串在比對串中出現的位置。

設比對串長度為n，模式串長度為m。

顯然暴力的時間複雜度是 O ( n m ) O(nm) O(nm)

但是想想可以發現，每次比對時一旦失配所有的相同資訊全部丢掉。

其中綠色部分是已比對部分，紅色則是失配部分

我們假設四塊藍色部分都相同

那麼可以直接這樣比對

實際上就是從這裡開始

至于預處理前後段相同部分，其實類似上面，隻不過是自己比對自己

如果失配就不斷疊代，具體不細述因為太水

時間複雜度 O ( n + m ) O(n+m) O(n+m)

code

# include <iostream>
# include <cstdio>
# include <cstring>
# define fo(a,b,c) for (a=b; a<=c; a++)
# define fd(a,b,c) for (a=b; a>=c; a--)
using namespace std;

char s[100000];
char t[100000];
int next[100000];
int i,j,k,l,len;

int main()
{
	scanf("%s",s);
	scanf("%s",t);
	len=strlen(t)-1;
	
	j=-1;
	next[0]=-1;
	fo(i,1,len)
	{
		while ((j>-1) && (t[j+1]!=t[i]))//不斷疊代
		j=next[j];
		
		if (t[j+1]==t[i])//如果比對成功就擴充
		j++;
		
		next[i]=j;
	}
	
	j=-1;
	fo(i,0,strlen(s)-1)
	{
		while ((j>-1) && (t[j+1]!=s[i]))//不斷疊代
		j=next[j];
		
		if (t[j+1]==s[i])//如果比對成功就擴充
		j++;
		
		if (j==len)//找到就輸出，并重新比對
		{
			cout<<i-len<<endl;
			j=next[j];
		}
	}
	
	return 0;
}
           

例題

JZOJ5096. 【GDOI2017 day1】房屋購置

Description

濤濤最近準備要結婚了，但這在這之前他需要買套房子。買房子的确是人生大事喲，是以濤濤要好好斟酌。

于是他去房屋中介網上爬到了各種房子的資料，并得到了這些房子的特征，但是現在有一個問題感到很困惑， 但他知道你程式設計賊 6，是以希望你能幫幫他。

現在有 N 幢房子，每幢房子用一個字元串 si 來描述。但同樣的房子不同的開發商會用不同的詞彙來描述。

某些字元串存在縮寫，例如 swimmingpool 可以簡寫為 pool 。

現在有 M 條特征的簡寫規則，每條規則包含兩個字元串 ai , bi , 表示将所有子串中的 ai 替換成 bi。

一個字元串可能會被同一條規則比對多次，優先替換最左邊的，且新生成的字元串會不會被重新用于該規則 的比對。不同的規則之間按照嚴格的順序關系執行 (詳見樣例)。

現在你需要對已有的 N 條字元串通過 M 條有順序的替換規則進行縮寫。

Input

第一行有兩個正整數 N，M，代表 N 幢房子，和 M 條替換規則。

接下來 N 行，每行一個字元串 si

接下來 M 行，每行兩個字元串 ai , bi，中間用空格隔開。

保證所有輸入的字元串隻會出現小寫字母。

Output

輸出 N 行每行一個字元串，代表特征替換後的字元串。

Sample Input

Sample Input1:

1 1

aaaaaaa

aaa ba

Sample Input2:

1 1

ababababc

aba a

Sample Input3:

3 3

swimmingswimmingpool

catallow

dogallow

cat pet

dog pet

swimmingpool pool

Sample Input4:

2 3

aaaabbb

bbbbaaa

aaaa cc

cbbb a

bbbb a

Sample Output

Sample Output1:

babaa

Sample Output2:

ababc

Sample Output3:

swimmingpool

petallow

petallow

Sample Output4:

ca

aaaa

Data Constraint

20% 的資料：1 ≤ |si |, |ai |, |bi | ≤ 100 (|s| 表示字元串 s 的長度)

50% 的資料：1 ≤ |si |, |ai |, |bi | ≤ 30000

100% 的資料：1 ≤ |si |, |ai |, |bi | ≤ 100000, 1 ≤ N, M ≤ 20, |ai | ≥ |bi |。

題解

直接搞就行了。。。

code

由于是N久前Pascal寫的，是以可(wu)能(bi)不優美

var
        a:array[1..20,0..200000] of longint;
        b:array[1..20,0..200000] of longint;
        s1,s2:array[0..200000] of longint;
        next:array[0..200000] of longint;
        n,m,i,j,k,l,len,ii,last:longint;
        bz,bz2:boolean;
        ch:char;
begin
        assign(Input,'house.in'); reset(Input);
        assign(Output,'house.out'); rewrite(Output);

        readln(n,m);

        for i:=1 to n do
        begin
                read(ch);
                while ch in['a'..'z'] do
                begin
                        inc(a[i,0]);
                        a[i,a[i,0]]:=ord(ch);

                        read(ch);
                end;
                readln;
        end;

        for i:=1 to m do
        begin
                s1[0]:=0;
                s2[0]:=0;

                read(ch);
                while ch<>' ' do
                begin
                        inc(s1[0]);
                        s1[s1[0]]:=ord(ch);

                        read(ch);
                end;

                read(ch);
                while ch in['a'..'z'] do
                begin
                        inc(s2[0]);
                        s2[s2[0]]:=ord(ch);

                        read(ch);
                end;
                readln;

                k:=0;
                for j:=2 to s1[0] do
                begin
                        while (k>0) and (s1[k+1]<>s1[j]) do
                        k:=next[k];

                        if s1[k+1]=s1[j] then
                        inc(k);

                        next[j]:=k;
                end;

                for k:=1 to n do
                begin
                        l:=0;
                        len:=a[k,0];
                        a[k,0]:=0;

                        while l<=len do
                        begin
                                bz:=false;
                                bz2:=false;

                                last:=l;
                                j:=0;
                                while (j<s1[0]) and (l<=len) do
                                begin
                                        inc(l);

                                        while (j>0) and (a[k,l]<>s1[j+1]) do
                                        j:=next[j];

                                        if a[k,l]=s1[j+1] then
                                        inc(j);
                                end;

                                if j<s1[0] then
                                break;

                                j:=next[j];

                                for ii:=last+1 to l-s1[0] do
                                begin
                                        inc(a[k,0]);
                                        a[k,a[k,0]]:=a[k,ii];
                                end;
                                for ii:=1 to s2[0] do
                                begin
                                        inc(a[k,0]);
                                        a[k,a[k,0]]:=s2[ii];
                                end;
                        end;

                        if last<len then
                        for l:=last+1 to len do
                        begin
                                inc(a[k,0]);
                                a[k,a[k,0]]:=a[k,l];
                        end;
                end;
        end;

        for i:=1 to n do
        begin
                for j:=1 to a[i,0] do
                write(chr(a[i,j]));
                writeln;
        end;

        close(Input); close(Output);
end.
           

AC自動機

全稱是Aho-Corasick

可以支援多模式串比對（相比之下，KMP隻能支援單模式串比對）

思想類似在trie上建KMP

（不懂trie可以自己去找資料或腦補）

AC自動機中最重要的思想就是fail指針。

定義fail[x]=y，則滿足y節點是x節點的最長字尾

比如"bac"是"aba bac"的字尾。

特殊的，如果x節點是根節點的兒子，則将fail[x]設為根節點。

那麼上圖的fail指針如下圖所示

fail指針類似KMP的next數組，從父節點不斷往上跳，如果跳到某個節點有和目前結點一樣的兒子，就把fail設為那個兒子。

是以AC自動機=trie+KMP

摘自http://blog.csdn.net/a_crazy_czy/article/details/48029883

設比對串長度為n，模式串共m個，第i個記為si。

可以證明AC自動機時間複雜度為O(n+∑length(si))

code

# include <iostream>
# include <cstdio>
# include <cstring>
# define fo(a,b,c) for (a=b; a<=c; a++)
# define fd(a,b,c) for (a=b; a>=c; a--)
using namespace std;

int n,i,j,k,l,len,h,t;
char s[1000];
char tt[1000];
int T[100000][26];
char ch[100000];
bool bz[100000];
int fa[100000];
int fail[100000];
int d[100000];

void _new(int t,char c)
{
	len++;
	T[t][int(c)-97]=len;
	fa[len]=t;
	ch[len]=c;
}

void _printf(int t)
{
	if (t>1)
	_printf(fa[t]);
	else
	{
		printf("\n");
		printf("%d\n",i+1);
		
		return;
	}
	printf("%c",ch[t]);
}

int main()
{
	scanf("%d",&n);
	scanf("%s",s);
	
	len=1;
	fo(i,1,n)//建trie
	{
		scanf("%s",tt);
		
		k=1;
		fo(j,0,strlen(tt)-1)
		{
			if (!T[k][int(tt[j])-97])
			_new(k,tt[j]);
			k=T[k][int(tt[j])-97];
		}
		bz[k]=1;
	}
	
	fail[1]=1;
	fo(i,0,25)//初始化根節點的兒子的fail
	fail[T[1][i]]=1;
	h=0;
	t=1;
	d[1]=1;
	while (h<t)//建fail指針
	{
		h++;
		fo(i,0,25)
		if (T[d[h]][i])
		{
			d[++t]=T[d[h]][i];
			
			if (d[h]>1)
			{
				j=fail[d[h]];
				while ((j>1) && (!T[j][i]))//不斷疊代
				j=fail[j];
				if (T[j][i])
				fail[d[t]]=T[j][i];
				else
				fail[d[t]]=1;
			}
		}
	}
		
	j=1;
	fo(i,0,strlen(s)-1)//比對
	{
		k=int(s[i])-97;
		
		while ((j>1) && (!T[j][k]))
		j=fail[j];
		
		if (T[j][k])//如果找到就往下走
		{
			j=T[j][k];
			if (bz[j])
			_printf(j);
		}
		l=j;
		while (l>1)//判斷目前位置的字尾是否存在于模式串中（可能會重疊）
		{
			l=fail[l];
			if (bz[l])
			_printf(l);
		}
	}
	
	return 0;
}
           

例題

JZOJ3472. 【NOIP2013模拟聯考8】比對(match)

Description

給定k個字元串以及長度為n的母串可選字母的集合，問母串要完整出現給定的k個字元串的方案數，答案模1000000007，字元僅包含小寫字母。

Input

第一行兩個整數n、k，表示字元串的長度和給定字元串的個數。

接下來k行每行一個字元串。

接下來一行1個整數m表示可選字母集合内元素個數。

接下來一行給出一個長為m的字元串，表示字母的集合（可能有重複）。

Output

一個整數ans，表示方案數。

Sample Input

3 2

cr

rh

4

acrh

Sample Output

1

【樣例解釋】

隻有crh符合。

Data Constraint

30%的資料n<=10，m<=3。

60%的資料n<=40。

另有10%的資料k=0。

另有10%的資料m=1。

100%的資料n<=100，m<=10，k<=8，給定字元串長度<=30。

題解

狀壓Dp+AC自動機

設f[i][j][k]表示目前枚舉到字元串第i位，在AC自動機上位置為j，比對成功的字元串狀态為k（狀壓）

然後建好AC自動機後搞一遍就行了。

code

# include <iostream>
# include <cstdio>
# include <cstring>
# define fo(a,b,c) for (a=b; a<=c; a++)
# define fd(a,b,c) for (a=b; a>=c; a--)
# define mod 1000000007
using namespace std;

int p[9]={0,1,2,4,8,16,32,64,128};
int n,m,i,j,k,l,len,h,t,L,J,K,I,ii;
bool ch[26];
char tt[1000];
int T[90][26];
int bz[90];
int CH[90];
int fa[90];
int fail[90];
int d[90];
int f[101][90][256];
long long ans;
char Ch;

void _new(int t,char c)
{
	len++;
	T[t][int(c)-97]=len;
	fa[len]=t;
}

void Aho_Corasick()
{
	scanf("%d%d",&n,&l);
	L=p[l]*2-1;
	
	len=1;
	fo(i,1,l)
	{
		scanf("%s",tt);
		
		k=1;
		fo(j,0,strlen(tt)-1)
		{
			if (!T[k][int(tt[j])-97])
			_new(k,tt[j]);
			k=T[k][int(tt[j])-97];
		}
		bz[k]=i;
	}
	
	fail[1]=1;
	fo(i,0,25)
	fail[T[1][i]]=1;
	h=0;
	t=1;
	d[1]=1;
	while (h<t)
	{
		h++;
		fo(i,0,25)
		if (T[d[h]][i])
		{
			d[++t]=T[d[h]][i];
			
			if (d[h]>1)
			{
				j=fail[d[h]];
				while ((j>1) && (!T[j][i]))
				j=fail[j];
				if (T[j][i])
				fail[d[t]]=T[j][i];
				else
				fail[d[t]]=1;
			}
		}
	}
}

int main()
{
	Aho_Corasick();
	
	scanf("%d\n",&m);
	fo(i,1,m)
	{
		scanf("%c",&Ch);
		CH[i]=int(Ch)-97;
	}
	
	if (len==1)
	{
		ans=1;
		fo(i,1,n)
		ans=(ans*m)%mod;
		
		printf("%d\n",ans);
		return 0;
	}
	
	f[0][1][0]=1;
	fo(i,0,n-1)
	{
		fo(j,1,len)
		{
			fo(k,0,L)
			if (f[i][j][k])
			{
				fo(ii,1,m)
				{
					l=CH[ii];
					
					J=j;
					K=k;
					while ((J>1) && (!T[J][l]))
					J=fail[J];
					
					if (T[J][l])
					J=T[J][l];
					I=J;
					while (I>1)
					{
						if (bz[I])
						K|=p[bz[I]];
						
						I=fail[I];
					}
					
					f[i+1][J][K]=(f[i+1][J][K]+f[i][j][k])%mod;
				}
			}
		}
	}
	
	ans=0;
	fo(i,1,len)
	ans=(ans+f[n][i][L])%mod;
	
	printf("%d\n",ans);
	
	return 0;
}
           

回文自動機

用來處理回文子串的問題。

1、求回文子串的種類。

2、求每種回文子串出現次數。

3、求比對串的字首中的回文子串。

4、求以下标i為結尾的回文子串個數。

思想跟AC自動機類似，每個節點都代表一個回文串

則每個節點都可以向兩邊同時加一個字元來變成新的回文串。

定義fail[x]=y表示x的最長字尾位置是y

因為回文串分奇偶性，是以定義兩個根

偶數根長度為0，奇數根長度為**-1**（沒錯就是-1，因為可以通過擴充得到長度為1的串）

然後偶數根的fail設為奇數根。

每次從目前節點（初始設為偶數根）擴充時，沿着fail指針一直跳，直到發現某個串可以擴充就擴充。

如果擴充了節點，那麼新節點的cnt（計數）設為1，否則+1

每次擴充長度+2

如果擴充了一個新節點，怎樣求它的fail指針？

比如說現在找到了一個可以擴充的節點

那麼它的字尾一定是這樣的

根據回文的性質，藍色部分一定是一個回文串

是以隻需要沿着fail指針繼續向上跳來找一個能擴充的點

能擴充的點不僅是要有相應的兒子，還要能在目前情況下擴充

（就是上面這點坑了我一個小時）

找到後把fail指針設為其兒子。

（如果沒有找到就把fail設為偶數根）

還有一點，因為每個長串包含了短串，是以最後要從後往前沿着fail來累加cnt。

其實了解了AC自動機後學這個并不難

時間複雜度 O ( ∣ S ∣ ) O(|S|) O(∣S∣)即 O ( n ) O(n) O(n)

然而我并不會證

例題

JZOJ3654. 【APIO2014】回文串

也就是本算法的出處

（補充一下，回文樹是由戰鬥民族的大佬于2014年發明的）

Description

考慮一個隻包含小寫拉丁字母的符串 s。我們定義 s的一個子串 t的“出現值”為 t在 s中的出現次數乘以t的長度。 請你求出s的所有 回文子串中的最大出現值。

Input

輸入隻有一行，為一個隻包含小寫字母 (a−z) 的非空字元串 s。

Output

輸出 一個整數，為 所有 回文子串 的最大 出現 值。

Sample Input

輸入1：

abacaba

輸入2：

www

Sample Output

輸出1：

7

輸出2：

4

題解

裸題瞎搞。

code

# include <iostream>
# include <cstdio>
# include <cstring>
# define fo(a,b,c) for (a=b; a<=c; a++)
# define fd(a,b,c) for (a=b; a>=c; a--)
# define max(x,y) (x>y?x:y)
using namespace std;

int tr[300010][26];
int fa[300010];
long long len[300010];
long long cnt[300010];
char s[300010];
int i,j,k,l,n,last,L;
long long ans;

char ch[300010];
int f[300010];

void New(int t,int x)
{
	n++;
	tr[t][x]=n;
	
	len[n]=len[t]+2;
	ch[n]=char(x+97);
	f[n]=t;
}

int main()
{
	freopen("palindrome.in","r",stdin);
	freopen("palindrome.out","w",stdout);
	
	scanf("%s",&s);
	L=strlen(s);
	fd(i,L,1)
	s[i]=s[i-1];
	s[0]=' ';
	
	n=1;
	fa[0]=1;
	fa[1]=1;
	len[0]=0;
	len[1]=-1;
	last=0;
	
	fo(i,1,L)
	{
		k=int(s[i])-97;
		
		while (s[i]!=s[i-len[last]-1])//不斷疊代查找
		last=fa[last];
		
		j=fa[last];
		while ((len[j]>-1) && (s[i]!=s[i-len[j]-1]))//繼續向上擴充
		j=fa[j];
		j=tr[j][k];
		
		if (!tr[last][k])//建立節點
		{
			New(last,k);
			fa[tr[last][k]]=j;
		}
		last=tr[last][k];//從目前點轉移到子樹
		cnt[last]++;
	}
	
	fd(i,n,2)
	{
		cnt[fa[i]]+=cnt[i];//累加答案
		ans=max(len[i]*cnt[i],ans);
	}
	
	printf("%lld\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}
           

參考資料

Palindromic Tree——回文樹【處理一類回文串問題的強力工具】

論如何優雅的處理回文串 - 回文自動機詳解.

回文樹介紹(Palindromic Tree)