2015ACM/ICPC亚洲区沈阳站-重现赛 B

题意:给你\(n\)个字符串,\(s_1,s_2,...,s_n\),对于\(i(1\le i\le n)\),找到最大的\(i\),并且满足\(s_j(1\le j<i)\)不是\(s_i\)的子串.
题解:直接\(O(n^2)\)然后跑kmp匹配,这里注意要剪枝,不然会T,也就是说对于前\(i-1\)个串,如果它是后面某个串的子串,那么我们就不用对它跑kmp,因为它后面的某个串包含了它.

代码:

int t;

int n;

string s[N];

int ne[N];

bool st[N];

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>t;

    int cnt=1;

    while(t--){

    	 cin>>n;

    	 me(st,false,sizeof(st));

   		 for(int i=1;i<=n;++i){

    		cin>>s[i];

    		s[i]=" "+s[i];

  		  }

  		  int ans=-1;

  		  for(int i=1;i<=n;++i){

    		for(int j=1;j<i;++j){

    			if(st[j]) continue;

    			string p=s[j];

    			string ss=s[i];

    			bool flag=false;

    			for(int k=2,t=0;k<(int)p.size();++k){

    				while(t!=0 && p[k]!=p[t+1]) t=ne[t];

    				if(p[k]==p[t+1]) t++;

    				ne[k]=t;

    			}

    			for(int k=1,t=0;k<(int)ss.size();++k){

    				while(t!=0 && ss[k]!=p[t+1]) t=ne[t];

    				if(ss[k]==p[t+1]) t++;

    				if(t==(int)p.size()-1){

    					flag=true;

    					st[j]=true;

    					break;

    				}

    			}

    			if(!flag){

    				ans=max(ans,i);

    				break;

    			}

    		}

  	  }

  	 	 cout<<"Case #"<<cnt<<": "<<ans<<endl;

  		 cnt++;

    }

    return 0;

}

巴特西

2015ACM/ICPC亚洲区沈阳站-重现赛 B - Bazinga (KMP)

最新文章

热门文章