给出一个字符串,求一个子串x,令w=xx,表示x的连接,如x=ab则w=abab,w在给出的字符串中出现并x是最长的。如给出”ababc”则结果是ab。并给出算法的时间复杂度。
- #include “stdafx.h”
-
- int CalcMaxNumOfConnnectedStr( const char *szStr ){
- if( szStr == NULL ) return 0;
-
- int len = strlen( szStr );
- int curLen = len/2;
- for( ; curLen > 0; curLen– )
- {
- for( int idx = 0; idx <= len - 2*curLen; idx++ ){
- if( strncmp( szStr + idx, szStr + curLen + idx, curLen) == 0 )
- return curLen;
- }
- }
-
- return 0;
- }
-
- int main(){
- char str[20];
- while( cin >> str )
- cout << CalcMaxNumOfConnnectedStr( str ) << endl;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
\