#C241002B. 子串结构

标签（Label）

• kmp

网址（Website）

题目详情 - 子串结构 - Super

题解 - 子串结构 - Super

题解（Solution）

$\qquad$如果出现包含，包含一次答案就是长度长的那个，包含多次就是无解，跑一次 $\mathrm{kmp}$ 即可。

$\qquad$考虑处理不包含的情况，发现母串匹配到第 $i=n$ 位（最后一位）时，对应的子串第 $j$ 位就是最长公共前后缀，字符串 $a$ 和 $b$ 都可以作为母串，分别跑一次 $\mathrm{kmp}$ 再进行匹配就是最后的答案。这样可以拿到 $95pts$ 。

$\qquad$发现 $95pts$ 有很多重复的遍历，这样会导致最后一个点 $\mathrm{TLE}$ ，发现在 $a,b$ 两串中间加一个字符（例如 '#' ）然后合在一起，只需要跑两次 $\mathrm{kmp}$ ，最后输出两串总和（$n+m$）减去两次 $\mathrm{kmp}$ 中大一点的 $pi[n+m]$ 即可。

代码（Code）

95pts

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f;
const int N = 2012345;
bool ST;

int pi[N];
void pre_kmp(char *s){
	int n = strlen(s+1);
	pi[1] = 0;
	for(int i=2,j=0;i<=n;i++){
		while(j&&s[i]!=s[j+1]) j=pi[j];
		if(s[i]==s[j+1]) j++;
		pi[i]=j;
	}
}

inline int check(char *s, char *t){
	int n = strlen(s+1), m = strlen(t+1);
	int res = 0;
	for(int i=1,j=0;i<=n;i++){
		while(j && s[i] != t[j+1]) j = pi[j];
		if(s[i]==t[j+1]) j++;
		if(j==m) res++;
	}return res;
}

inline int cal(char *s, char *t){
	int n = strlen(s+1);
	int res = 0;
	for(int i=1,j=0;i<=n;i++){
		while(j && s[i] != t[j+1]) j = pi[j];
		if(s[i]==t[j+1]) j++;
		if(i==n) res = j;//最大匹配数目 
	}return res;
}

char a[N],b[N];
inline void solve(){
	cin>>(a+1)>>(b+1);
	if(strlen(a+1) > strlen(b+1)) swap(a,b);//保证b更大 
	
	pre_kmp(a);
	
	int t = check(b, a);//b里面有多少个a 
	if(t==1) cout<<strlen(b+1)<<'\n';
	else if(t>1) cout<<"-1\n";
	else{//此时a,b不重合 
		int res = cal(b,a);//b后面接a 
		pre_kmp(b), res = max(res, cal(a,b));//a后面接b 
		cout<<strlen(a+1)+strlen(b+1)-res<<'\n';
	}
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	int T = rd(), Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}

100pts

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f;
const int N = 2012345;
bool ST;

int pi[N];
void pre_kmp(string s){
	int n = s.length();
	pi[1] = 0;
	for(int i=2,j=0;i<n;i++){
		while(j&&s[i]!=s[j+1]) j=pi[j];
		if(s[i]==s[j+1]) j++;
		pi[i]=j;
	}
}

string a,b,c;
inline void solve(){
	cin>>(a)>>(b);
	if(a.length() > b.length()) swap(a,b);//保证b更大 
	
	c = " " + a + "#" + b;
	pre_kmp(c);
	
	int t = 0, n = c.length()-1;
	For(i,a.length()+1,n) t += pi[i]==(int)a.length();
	
	if(t==1){cout<<b.length()<<'\n';return;}
	if(t>1){cout<<"-1\n";return;}
	
	int mx = pi[n];
	
	c = " " + b + "#" + a;
	pre_kmp(c);
	
	cout<<n-1-max(mx,pi[n])<<'\n';
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	int T = rd(), Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}