这显然是道裸的kmp题,
~~ 但由于我看错题目,我不知道怎么做~~(我以为换过的字符串可以再换)
仔细看看题目,发现题目就是到裸题
但细节比较难改:
#include<bits/stdc++.h>
using namespace std;
const int N=30,LON=100010;
int n,m;
char s[N][LON],a[N][LON],b[N][LON];
int kmp[N];
inline void get_kmp(int x)
{
int len=strlen(a[x]+1);
int j=0;
kmp[j]=0;
for(int i=2;i<=len;i++){
while(a[x][i]!=a[x][j+1]&&j>0) j=kmp[j];
if(a[x][i]==a[x][j+1]) {
j++;
}
kmp[i]=j;
int g=kmp[i];
}
}
inline void cal(int x)
{
int lon=strlen(s[x]+1);
for(register int j=1;j<=m;j++){
get_kmp(j);
int len=strlen(a[j]+1);
int strt=0;
for(register int k=1;k<=lon;k++){
if(s[x][k]=='1') continue;
while(s[x][k]!=a[j][strt+1]&&strt>0) strt=kmp[strt];
if(s[x][k]==a[j][strt+1]) {
strt++;
}
if(strt==len){
strt=0;
int ll=strlen(b[j]+1);
int o=k,sum=0;
for(register int i=ll;i>=1&&sum<=len;i--)
{
while(s[x][o]=='1') o--;
sum++;
s[x][o]=b[j][i];
o--;
}
if(sum<len){
for(register int i=o;i>0&&sum<len;i--)
{
while(s[x][i]=='1') i--;
sum++;
s[x][i]='1';
}
}
}
}
}
for(register int i=1;i<=lon;i++){
if(s[x][i]=='1') continue;
printf("%c",s[x][i]);
}
puts("");
}
inline void solve(){
for(int i=1;i<=n;i++){
cal(i);
}
}
int main(){
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(register int j=1;j<=m;j++){
scanf("%s %s",a[j]+1,b[j]+1);
}
solve();
}