模板，但是对这个算法还是不太清楚,真实不明觉厉....
1 #include2 #include 3 #include 4 #pragma warning ( disable : 4996 ) 5 using namespace std; 6 7 inline int Max(int a,int b) { return a>b?a:b; } 8 inline int Min(int a,int b) { return a>b?b:a; } 9 const int inf = 0x3f3f3f3f;10 const int maxn = 1e5+1e4+5;11 12 char str[maxn];13 char nstr[maxn<<1];14 int maxlen[maxn<<1];15 int len, plen, ans;16 17 void init()18 {19 memset( nstr, 0, sizeof(nstr) );20 memset( maxlen, 0, sizeof(maxlen) );21 len = strlen(str); 22 nstr[0] = '$'; nstr[1] = '#';23 24 int j = 2;25 for ( int i = 0; i < len; i++ )26 {27 nstr[j++] = str[i];28 nstr[j++] = '#';29 }30 nstr[j] = '\0';31 plen = j;32 }33 34 void solve()35 {36 ans = -1;37 int id, mx = 0;38 39 for ( int i = 1; i < plen; i++ )40 {41 if( i < mx )42 maxlen[i] = Min( maxlen[2*id-i], mx-i );43 else44 maxlen[i] = 1;45 46 while( nstr[i-maxlen[i]] == nstr[i+maxlen[i]] )47 maxlen[i]++;48 49 if ( mx < i + maxlen[i] )50 {51 id = i;52 mx = i + maxlen[i];53 }54 ans = Max(ans, maxlen[i]-1);55 }56 }57 58 int main()59 {60 while ( ~scanf("%s", str) )61 {62 init();63 solve();64 printf( "%d\n", ans );65 }66 return 0;67 }
又做了一道几乎模板的题（吉哥系列故事——完美队形II），终于对马拉车有点理解了，这算法实在太巧妙了！
和模板几乎一样，只不过增多了个左半边要升序排列罢了
1 #include2 #include 3 #include 4 #pragma warning ( disable : 4996 ) 5 using namespace std; 6 7 inline int Max(int a,int b) { return a>b?a:b; } 8 inline int Min(int a,int b) { return a>b?b:a; } 9 const int inf = 0x3f3f3f3f;10 const int maxn = 1e5+5;11 12 int maxl[maxn<<1];13 int str[maxn], nstr[maxn<<1];14 int N, ans, plen;15 16 void init()17 {18 memset( maxl, 0, sizeof(maxl) );19 memset( nstr, 0, sizeof(nstr) );20 nstr[0] = 0; nstr[1] = -1;21 22 int j = 2;23 for( int i = 0; i < N; i++ )24 { nstr[j++] = str[i]; nstr[j++] = -1; }25 nstr[j] = -2;26 plen = j;27 }28 29 void solve()30 {31 ans = -1;32 int id, mx = 0;33 for ( int i = 1; i < plen; i++ )34 {35 if(i < mx) 36 maxl[i] = Min(maxl[2*id-i], mx-i);37 else 38 maxl[i] = 1;39 40 while( nstr[i-maxl[i]]==nstr[i+maxl[i]] && nstr[i-maxl[i]]<=nstr[i-maxl[i]+2] )41 maxl[i]++;42 if(mx < i + maxl[i])43 { id = i; mx = i + maxl[i]; }44 45 ans = Max(ans, maxl[i]-1);46 }47 }48 49 int main()50 {51 int all; cin >> all;52 while (all--)53 {54 cin >> N;55 for( int i = 0; i < N; i++ )56 scanf( "%d", &str[i] );57 init();58 solve();59 60 printf( "%d\n", ans );61 }62 return 0;63 }