撸呀撸的左手(KMP+DP)

题目描述

撸呀撸很迷茫，因为他的左手总是不受控制，做一些不雅的事情。于是撸呀撸一狠心，决定戒撸。没想到，他的左手受不了寂寞，一闲下来就在键盘上各种乱敲。

唔，神奇的左手表示，safasfasaafafsfafasffsfsfsffsfddfafdfsfadffafadfafadfadfafadfsfa……

他发现敲出来的字符串有一定规律：如果将字符串划分成若干部分，那么每部分都可由其子串重复若干次得到。
“若干次”往往大于1，但也可以为1。小撸想请你算一算：用最优的方法划分字符串，然后将各部分替换成其最短的连续重复子串，得到的字符串的最小长度是多少p>

输入格式

一行字符，都是英文小写字母。

输出格式

一个正整数，是最小长度。

样例输入

bababacacac

样例输出

5  1 #include 
 2 #include 
 3 #include 
 4  using  namespace std ;
 5  #define inf 0x7fffffff
 6  #define MAXN 5010
 7  int pre[ MAXN ] , f[ MAXN ] , n ;
 8  char s[ MAXN ] , st[ MAXN ] ;
 9 
10  void kmp(  int len ) {
11     pre[  1 ] =  0 ;
12      for (  int i =  1 , j =  0 ; i ++ < > 13          for ( ; j && st[ j +  1 ] != st[ i ] ; j = pre[ j ] ) ;
14          if ( st[ j +  1 ] == st[ i ] ) ++ j ;
15         pre[ i ] = j ;
16     }
17 }
18 
19  int main(  ) {
20     scanf(  “ %s “ , s +  1 ) ;
21     n = strlen( s +  1 ) ;
22     f[  0 ] =  0 ;
23      for (  int i =  0 ; i ++ < > 24         f[ i ] = inf ;
25          int len =  0 ;
26          for (  int j = i ; j ; — j ) st[ ++ len ] = s[ j ] ;
27         kmp( len ) ;
28          for (  int j = i –  1 ; j >=  0 ; — j ) {
29              int l = i – j , cost ;
30             cost = ( l % ( l – pre[ l ] ) ) bsp;l : ( l – pre[ l ] ) ;
31             f[ i ] = min( f[ i ] , f[ j ] + cost ) ;
32         }
33     }
34     printf(  “ %dn “ , f[ n ] ) ;
35      return  0 ;

36 } 

相关资源：2017齐鲁软件大赛比赛基于Funcode平台的程序设计_funcode安装包…