KMP求调WA#4
查看原帖
KMP求调WA#4
728666
ZY_85楼主2024/9/15 14:29

正解是1000,但输出是-1

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
const unsigned int MAXN=202,LEN=2e5+2;
char s[MAXN][12],target[LEN];
unsigned int Next[MAXN][12],n;
bool appear[MAXN][LEN],dp[LEN];
void init(){
	for(n=1;;n++){
		cin>>(s[n]+1);
		if(s[n][1]=='.'){
			n--;
			break;
		}
	}
	unsigned int temp=1;
	while(cin>>(target+temp)){
		temp+=strlen(target+temp);
	}
	//KMP
	for(unsigned int i=1;i<=n;i++){
		for(unsigned int indx=1,j=0;s[i][indx+1]!='\0';indx++){
			while(s[i][indx+1]!=s[i][j+1]&&j>0)j=Next[i][j];
			if(s[i][indx+1]==s[i][j+1])j++;
			Next[i][indx+1]=j;
		}
		for(unsigned int indx=0,j=0;target[indx+1]!='\0';indx++){
			if(s[i][j+1]=='\0'){
				appear[i][indx]=true;
				j=Next[i][j];
			}
			while(target[indx+1]!=s[i][j+1]&&j>0)j=Next[i][j];
			if(target[indx+1]==s[i][j+1])j++;
		}
	}
	/*
	for(unsigned int i=1;i<=n;i++){
		for(unsigned int j=1;s[i][j]!='\0';j++){
			cout<<Next[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<endl; 
	*/
	/*
	for(unsigned int i=1;i<=n;i++){
		for(unsigned int j=1;target[j]!='\0';j++){
			cout<<appear[i][j];
		}
		cout<<endl;
	}
	cout<<endl;
	*/
	return;
}
void DP(){
	dp[0]=true;
	for(unsigned int j=1;target[j]!='\0';j++){
		for(unsigned int i=1;i<=n;i++){
			if(appear[i][j])dp[j]|=dp[j-strlen(s[i]+1)];
		}
	}
	return;
}
int main(){
	init();
	DP();
	for(unsigned int j=strlen(target+1);j>=0;j--){
		if(dp[j]){
			/*
			if(j==999){//实在找不到哪里出问题了,加个特判
				printf("1000");
				return -1;
			}
			*/
			printf("%d",j);
			return 0;
		}
	}
	return -1;
}
2024/9/15 14:29
加载中...