找出一个字符串中重复出现的最长子串长度及开始位置
找出一个字符串中重复出现的最长子串长度及开始位置。如abcdewoiabwewog 中最长子串长度是3 即ewo
#include <stdlib.h> #include <string.h> int compare( const void* a, const void* b ) { return strcmp( *(const char**)a, *(const char**)b ); } int main() { const char* str = "abcdewoiabwewog"; ////////////////////// const size_t len = strlen( str ); const char* ps[len]; for( size_t i=0; i!=len; ++i ) ps[i] = str+i; qsort( ps, len, sizeof(ps[0]), &compare ); size_t maxlen = 0; size_t maxidx = 0; for( size_t i=0; i!=len-1; ++i ) { const char* a = ps[i]; const char* b = ps[i+1]; size_t idlen = 0; for( ; a[idlen]!='\0' && a[idlen]==b[idlen]; ++idlen ); if( idlen > maxlen ) { maxlen = idlen; maxidx = (a-str)<=(b-str) ? (a-str) : (b-str); } } printf( "start: %d; length: %d; value: %.*s\n", maxidx, maxlen, maxlen, str+maxidx ); return 0; }
#include <stdlib.h> #include <string.h> int main() { const char* str = "abcdewoiabwewog"; int f[100][100]={0},maxlen=0,len=strlen(str),start,i,j,k; for (i=1; i<len; i++) if (str[0]==str[i]) f[0][i]=1; for (i=1; i<len; i++) for (j=i+1; j<len; j++) { if (str[i]==str[j]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=0; if (f[i][j]>maxlen) { maxlen=f[i][j]; start=i-maxlen+1; } } printf("Maxlen=%d Start=%d End=%d\n",maxlen,start,start+maxlen-1); system("pause"); return 0; }