竞赛讨论区 > 正确率一直80% 测试点4 10 11 12过不了
头像
sunny_forever
发布于 2020-12-07 21:43
+ 关注

正确率一直80% 测试点4 10 11 12过不了

为什么一直对 80% 我裂开了 求大佬解惑 呜呜呜
#include <stdio.h>
#include <string.h>
#include <memory.h>
char s[1000005]; 
char ss[1000005];
char sss[1000005]; 
int next[1000005];
int next1[1000005];
void NEXT(char *s)
{
	int ll=strlen(s);
	next[0]=-1;
	int k=-1;
	for (int i=1;i<ll;i++)
    {	
    	while (k>-1&&s[i]!=s[k+1])
    		k=next[k];
		if (s[i]==s[k+1])
			k++;
		next[i]=k;
	}
	
}

int KMP(char *s1,char *s)  //s1 模板串    s主串 
{
	int l1=strlen(s1);
	int l=strlen(s);
	next1[0]=-1;
	int k=-1;
	for (int i=1;i<l1;i++)
    {	
    	while (k>-1&&s1[i]!=s1[k+1])
    		k=next1[k];
		if (s1[i]==s1[k+1])
			k++;
		next1[i]=k;
	}
	 	 k=-1;
	  for (int i=0;i<l;i++)
	  {
	  	while(k>-1&&s[i]!=s1[k+1])
	  		k=next1[k];
	  	if (s[i]==s1[k+1])
	  	    k++;
	  	 if (k==l1-1)
	  	     return 1;	 
	  }	  
	return 0;
}

int main()
{    
	scanf("%s",s);
	int l=strlen(s);
 	NEXT(s);
    
    int len=l;
     while (next[len-1]!=-1)  
   {
   	  len=next[len-1]+1;
   	 	 int k=0;
    memset(ss,0,sizeof(ss));
   	memset(sss,0,sizeof(sss));
    for (int i=len;i<l-len;i++)
 		    ss[k++]=s[i];  
   		 ss[k]='\0';      
			
		k=0;	
	for (int i=0;i<len;i++)	   //sss 模板串    ss主串 
	 	   sss[k++]=s[i];  
		sss[k]='\0';     
		
   	  if (KMP(sss,ss))      //sss 模板串    ss主串 
     {
     	printf("%s\n",sss);
     	return 0;
	   }  
	   
   }
   
    printf("Just a legend\n");
	return 0;
}


全部评论

(4) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐