疑问(悬关)
  • 板块灌水区
  • 楼主LYS_Lewis
  • 当前回复9
  • 已保存回复10
  • 发布时间2024/7/15 19:59
  • 上次更新2024/7/15 20:53:29
查看原帖
疑问(悬关)
805192
LYS_Lewis楼主2024/7/15 19:59

下面的代码开O2会RE,关O2就能正常运行,为什么?!!!

顺便在这里求调,希望有大佬能帮忙调到开O2也能通过。

谢谢!!!

#include<bits/stdc++.h>
using namespace std;
int T,minn = 100010,s[50][1000010],t[50][1000010],minpos = -1,st,l1,l2;
char S[1000010],F[1000010];

void dfs(int deep,int pos){
	if(deep==l2){
		if(pos-st<minn){
			minn = pos-st;
			minpos = st;
		}
		return;
	}
	int ch = F[deep]-'a';
	int newpos = t[ch][pos];
	if(newpos<pos)return;
	dfs(deep+1,newpos);
}

int main(){

	cin>>T;
	while(T--){
		minn = 100010,minpos = -1;
		cin>>S>>F;
		l1 = strlen(S);
		l2 = strlen(F);
        //cout<<l1<<" "<<l2<<"\n";
		if(l1==l2){
			cout<<F<<"\n";
			continue;
		}
		for(int i = 0;i<=26;i++){
			for(int j = 0;j<=100000;j++){
				t[i][j] = -1,s[i][j] = 0;
			}
		}
		for(int i = 1;i<=l1;i++){
			for(int j = 0;j<26;j++){
				if(S[i-1]-'a'==j){
					s[j][i] = s[j][i-1]+1;
					int k = i-1;
					while(s[j][k]==s[j][i]-1){
						t[j][k] = i;
						k--;
					}
					
				}
				else{
					s[j][i] = s[j][i-1];
				}
			} 
		}
		for(int i = 0;i<l1-l2;i++){
			if(F[0]==S[i]){
				st = i;
				dfs(1,i+1);
			}
			else continue;
		}
		for(int i = minpos;i<=minpos+minn-1;i++){
			cout<<S[i];
		}
		cout<<"\n";
	}
	return 0;
}
2024/7/15 19:59
加载中...