Simple application of KMP

【 Templates 】KMP string matching

P3375 【 Templates 】KMP string matching - Luogu | New ecology of computer science education (luogu.com.cn)

Answer key ：

1. Find out first s2 The value of the prefix and suffix array of the segment , And then find out s1 Segment and s2 Segment of the same character .

2. If the length of the same character segment is equal to s2 The length of is output i-j+1, And back to j The value of the prefix array of .

The code is as follows

#include<stdio.h>
#include<string.h>
char s[1000009],a[1000009];
int flag[1000009];// Store the longest prefix number  
int i,j;
int main()
{
	scanf("%s%s",s,a);
	int a1=strlen(a),b=strlen(s);
	int j=-1,i=0;
	flag[0]=-1;
	while(i<a1)
	{
		if(j==-1||a[j]==a[i])
		{
			flag[++i]=++j;
		}
		else
		j=flag[j];// to flash back  
	} 
	j=i=0;
	while(i<b) 
	{
		if(j==-1||s[i]==a[j])
		{
			i++;
			j++;
			if(j==a1)
			{
				printf("%d\n",i-j+1);
				j=flag[j];// to flash back 
			}
		} 
		else
		j=flag[j];
	}
	for(i=1;i<=a1;i++)
	printf("%d ",flag[i]); 
	return 0;
 } 

This is the code above s2 The value of the prefix and suffix array of the segment , Represents the current mismatch ,flag[s2 The array subscript +1] The value of is to be adjusted back to s2 The position of the array .

ABA
-1001

The code is as follows

#include<stdio.h>
#include<string.h>
char s[1000009],a[1000009];
int flag[1000009];// Store the longest prefix number  
int i,j;
int main()
{
	scanf("%s%s",s+1,a+1);
	int a1=strlen(a+1),b=strlen(s+1);
	for(i=2;i<=a1;i++)
	{
	while(j>0&&a[i]!=a[j+1])// Mismatch , Jump back  
	j=flag[j];
	flag[i]=a[i]==a[j+1]?++j:0;
	}
	j=0;
	for(i=1;i<=b;i++) 
	{
		while(j>0&&s[i]!=a[j+1]) 
		j=flag[j];
		if(s[i]==a[j+1])
		j++;
		if(j==a1)
		{
		printf("%d\n",i-j+1);
		j=flag[j];
		}
	}
	for(i=1;i<=a1;i++)
	printf("%d ",flag[i]); 
	return 0;
 } 

  This is the code above s2 The value of the prefix and suffix array of the segment , It means that if there is no match, you should call back s2 Where in the array .

ABA
001

 [USACO09OCT]Barn Echoes G

​​​​​​P2957 [USACO09OCT]Barn Echoes G - Luogu | New ecology of computer science education (luogu.com.cn)

Answer key ：

1. The meaning of the question is to judge the longest length of the part where the prefix of one string coincides with the suffix of the other string .

2. Obviously, this topic can be used kmp solve , Ideas as follows ,

        Two functions ： Determine the prefix and suffix array of the substring （ Prefix ）;

         Judge the coincidence length of the substring and the main string ,j The value of is the value of coincidence length . Because the prefix of one string coincides with the suffix of another string , therefore j The value of is the coincidence length .

3. Because you are not sure that the string is a substring, you need to judge both , Finally, take the maximum of the two . That is the final result .

4.kmp The first code above is used .

The code is as follows

#include<bits/stdc++.h>
using namespace std;
int flag[80];
char s1[80],s2[80];
void net(char a[],int len)
{
	int j=-1,i=0;
	flag[0]=-1;
	while(i<len)
	{
		if(j==-1||a[j]==a[i])
		{
			flag[++i]=++j;
		}
		else
		j=flag[j];// to flash back  
	} 
} 
int shu(char s[],int len1,char a[],int len2)
{
	net(s,len1);
	int j=0,i=0;
	while(i<len2)
	{
		if(j==-1||s[j]==a[i])
		{
			i++;
			j++;
		}
		else
		j=flag[j];// to flash back  
	}
	return j;
}
int main()
{
	scanf("%s",s1);
	scanf("%s",s2);
	int a,b;
	a=strlen(s1),b=strlen(s2);
	int a1,a2;
	a1=shu(s1,a,s2,b);
	a2=shu(s2,b,s1,a);
	printf("%d",max(a1,a2));
	return 0;
}

Compress Words

CF1200E Compress Words - Luogu | New ecology of computer science education (luogu.com.cn)

Answer key ：

1. What is the longest prefix in two words . Then discard this part .

2. I started by separating the two words and then calling 2 individual kmp The function result time is out of limit . After that, the two words are combined into a string （ Put the last word （ Prefix ） Spell the previous word （ suffix ） In front of ）, Here's to say string+ It's really easy to use ！！！ Call another kmp function （ A solution to the first problem ）, Find the prefix and suffix array of this string .

3. Find the prefix and suffix array of the string , Add the non overlapping part to the first word .

for(j=flag[s3.size()];j<s2.size();j++), Take the last value of the pre suffix array （s3.size()）, That is, the longest coincident length value , Start with this subscript , Add all the parts that do not overlap to the first word .

4. As a result, the time limit was exceeded , What do I do ？ Here again, I think that the longest overlapping length between two words does not exceed the length of the shortest word .t=min(s1.size(),s2.size()); Find out t value , Reuse substr Function will s2 The prefix string of ,s1 The suffix string of .

5. For some special cases

5
1101 1001 001001 101 010

Can be synthesized in s3 String at s2 And s1 Add something in the middle of the string to be intercepted . 

The code is as follows

#include<bits/stdc++.h>
using namespace std;
int flag[1000005],n;
void next(string a)//kmp
{
	int j=-1,i=0;
	flag[0]=-1;
	int len=a.size();
	while(i<len)
	{
		if(j==-1||a[j]==a[i])
		{
			flag[++i]=++j;
		}
		else
		j=flag[j];
	}
}
int main()
{
	cin>>n;
	string s1,s2,s3;
	cin>>s1;
	int m,j,t;
	for(m=0;m<n-1;m++)
	{
		cin>>s2;
		t=min(s1.size(),s2.size());
		s3=s2.substr(s2.size()-s2.size(),t)+'#'+s1.substr(s1.size()-t,t); 
		next(s3);
		for(j=flag[s3.size()];j<s2.size();j++)
		s1+=s2[j];
	}
	cout<<s1;
}

[BOI2009]Radio Transmission Wireless transmission

P4391 [BOI2009]Radio Transmission Wireless transmission - Luogu | New ecology of computer science education (luogu.com.cn)

Answer key ：

1. This question deepens my understanding of kmp Algorithm understanding , The second of the first code is used kmp solution .

2. The desired value is ： String length — The value of the array length in the array before the string suffix .

3. The value of array length in the suffix array before the string represents the longest coincident length , The non overlapping part is the length of the substring of the original composition string .

The code is as follows ：

#include<bits/stdc++.h>
using namespace std;
string s;
int n;
int net[10000009];
int kmp(string s)// Find the longest prefix  
{
	int j=0,i;
	int len=s.size();
	net[0]=0;
	s=' '+s;
	for(i=2;i<=len;i++)
	{
		while(j&&s[i]!=s[j+1])
		j=net[j];
		if(s[i]==s[j+1])
		j++;
		net[i]=j;
	}
	return net[len]; 
}
int main()
{
	scanf("%d",&n);
	cin>>s;
	int t=kmp(s);
	cout<<n-t;
	return 0;
}