>>84 合ってるかどうか検証して欲しい、文字列長1000に対して1秒かからないはず
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SRC_LEN 1000
int search_match_max(const char *a, const char *b){
int count=0, maximum=0;
for(;*a && *b;a++,b++){
if(*a==*b) count++;
else count=0;
if(count>maximum) maximum=count;
}
return maximum;
}
int main(void){
char src[SRC_LEN+1], tmp[SRC_LEN+1];
int i, srclen, count, maximum=0;
for(i=0;i<SRC_LEN;i++) src[i]=(rand()%3)+'a'; // テスト用文字列生成
src[i]='\0';
srclen=strlen(src);
for(i=0;i<srclen;i++) tmp[i]=src[srclen-1-i]; // 反転文字列生成
tmp[srclen]='\0';
for(i=0;i<srclen;i++){
count=search_match_max(&src[i], &tmp[0]);
if(count>maximum) maximum=count;
count=search_match_max(&src[0], &tmp[i]);
if(count>maximum) maximum=count;
}
puts(src);
printf("%d\n", srclen-maximum); // (削る文字数) = (文字列長) - (最大一致長)
return 0;
}