首页 > 代码库 > hdu--1867--kmp<kmp,怪我太sb>
hdu--1867--kmp<kmp,怪我太sb>
这题 做的时候 肯定自己短路了...
一开始 拿到手 思考了下 我就想 暴力做了...
我是想到kmp了 但我考虑错了 对于跳出循环那边 想错了 艹....
然后 就暴力 tle tle 。。。
然后 我去看了下 别人的解题报告 顿悟啊...
直接贴别人的AC代码吧 不想写了 心累啊
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 100010; 6 char str1[size]; 7 char str2[size]; 8 9 int solve( char* str1 , char* str2 , int& val )10 {11 int i , j , t , ans;12 int len1 = strlen(str1);13 int len2 = strlen(str2);14 ans = size*size;15 for( i = 0 ; i<len1 ; i++ )16 {17 t = i;18 j = 0;19 while( t<len1 && j<len2 && str1[t] == str2[j] )20 {21 t ++;22 j ++;23 }24 if( t==len1 )25 {26 val = i;27 ans = len2+i;28 break;29 }30 }31 return ans;32 }33 34 void outPut( int val , int ans , char* str1 , char* str2 )35 {36 for( int i = 0 ; i<val ; i++ )37 {38 cout << str1[i];39 }40 cout << str2 << endl;41 }42 43 int main()44 {45 cin.sync_with_stdio(false);46 int i , j , t;47 int val1 , ans1 , val2 , ans2 , ans , flag;48 while( cin >> str1 >> str2 )49 { 50 val1 = val2 = -1;51 ans1 = solve( str1 , str2 , val1 );52 ans2 = solve( str2 , str1 , val2 );53 ans = min( ans1 , ans2 ); 54 flag = strcmp(str1,str2);55 if( ans == size*size )56 {57 if( flag<0 )58 {59 cout << str1 << str2 << endl;60 }61 else62 {63 cout << str2 << str1 << endl;64 }65 }66 else67 {68 if( ans1 < ans2 )69 {70 outPut( val1 , ans1 , str1 , str2 );71 }72 else if( ans1 > ans2 )73 {74 outPut( val2 , ans2 , str2 , str1 );75 }76 else77 {78 if( flag<0 )79 {80 outPut( val1 , ans1 , str1 , str2 );81 }82 else83 {84 outPut( val2 , ans2 , str2 , str1 );85 }86 }87 }88 }89 return 0;90 }
暴力地 拿上来,...
1 复制代码 2 3 #include<iostream> 4 #include<cstdio> 5 #include<cstring> 6 7 using namespace std; 8 9 const int maxn=100010;10 11 int next[maxn];12 char s1[maxn],s2[maxn];13 14 void getnext(char *t){15 int len=strlen(t);16 int i=0,j=-1;17 next[0]=-1;18 while(i<len){19 if(j==-1 || t[i]==t[j]){20 i++;j++;21 next[i]=j;22 }else23 j=next[j];24 }25 }26 27 int KMP(char *s,char *t){28 int len1=strlen(s),len2=strlen(t);29 int i=0,j=0;30 getnext(t);31 while(i<len1 && j<len2){32 if(j==-1 || s[i]==t[j]){33 i++;j++;34 }else35 j=next[j];36 }37 if(i==len1)38 return j;39 return 0;40 }41 42 int main(){43 44 //freopen("input.txt","r",stdin);45 46 while(~scanf("%s%s",s1,s2)){47 int x=KMP(s1,s2);48 int y=KMP(s2,s1);49 if(x==y){50 if(strcmp(s1,s2)<0)51 printf("%s%s\n",s1,s2+x);52 else53 printf("%s%s\n",s2,s1+x);54 }else if(x>y)55 printf("%s%s\n",s1,s2+x);56 else57 printf("%s%s\n",s2,s1+y);58 }59 return 0;60 }
还是 去洗个澡吧...
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。