求助88分,样例能过,WA#6,8,悬一关
查看原帖
求助88分,样例能过,WA#6,8,悬一关
779349
JPGOJCZX楼主2023/12/24 15:31

rt

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
int len1, len2, f[N];
char s1[N], s2[N];
bool used[N];
string s;
void get_f(){
	f[0] = f[1] = 0;
	int i = 2, j = 1;
	while(i <= len2){
		while(j != 1 && s2[i] != s2[j])
			j = f[j - 1] + 1;
		if(s2[i] == s2[j])
			f[i++] = j++;
		else
			f[i++] = 0;
	}
}
int tot, ans[N];
void kmp(){
	int i = 1, j = 1;
	while(i <= len1){
		while(j != 1 && s1[i] != s2[j])
			j = f[j - 1] + 1;
		if(s1[i] == s2[j]){
			if(j == len2)
                ans[++tot] = i - len2 + 1;
			++i;
			++j;		
		} else
			++i;
	}	
}
int main(){
	scanf("%s%s", s1 + 1, s2 + 1);
	len1 = strlen(s1 + 1);
	len2 = strlen(s2 + 1);
    while(true){
        get_f();
        kmp();
        if(tot == 0)
            break;
        for(int i = 1; i <= tot; i++){
            int beg = ans[i];
            if(!used[beg])
                for(int j = ans[i]; j <= ans[i] + len2 - 1; j++)
                    used[j] = true;
        }
        s = "";
        for(int i = 1; i <= len1; i++)
            if(!used[i])
                s += s1[i];
        int len = s.length();
        for(int i = 1; i <= len; i++)
            s1[i] = s[i - 1];
        s1[len + 1] = '\0';   
        len1 = len;
        for(int i = 1; i <= tot; i++){
            int beg = ans[i];
            for(int j = ans[i]; j <= ans[i] + len2 - 1; j++)
                used[j] = false;
        }
//		cout << s1 + 1 << endl;
        for(int i = 1; i <= tot; i++)
            ans[i] = 0;
        tot = 0;
    }
    for(int i = 1; i <= len1; i++)
        printf("%c", s1[i]);
	return 0;
}
2023/12/24 15:31
加载中...