以前对这个算法不是很理解，只是知道有这个算法，需要的时候网上抄一下，现在大概有些理解了。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 string s; 8 void solve() { 9 cin >> s; 10 stringstream ss; 11 ss << '#'; 12 for (char x : s) 13 ss << x << '#'; 14 s = ss.str(); 15 int n = s.size(); 16 vector<int> dp(n, 0); 17 int mr, t; 18 t = mr = 0; 19 ll res = 0; 20 for (int i = 1; i < n; i++) { 21 if(i <= t + dp[t]) 22 dp[i] = min(t + dp[t] - i, dp[t * 2 - i]); 23 while(i - dp[i] - 1 >= 0 && i + dp[i] + 1 < n && s[i - dp[i] - 1] == s[i + dp[i] + 1]) 24 dp[i]++; 25 if(dp[i] + i >= dp[t] + t) 26 t = i; 27 //cout << dp[i] << endl; 28 res = res + (dp[i] + 1) / 2; 29 } 30 cout <<res <<endl; 31 } 32 33 int main() { 34 freopen("test.in", "r", stdin); 35 //freopen("test.out", "w", stdout); 36 solve(); 37 return 0; 38 }
贴一个hihocode的讲义，里面有manacher的详细讲解。