【題解】HDU 3336 Count the string

#include <iostream>
#include <string>
using namespace std;

int t, n, pos, f[200005];
long long ans;
string s;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n;
        cin >> s;
        pos = -1;
        f[0] = -1;
        ans = 0;
        for (int i = 1; i < n; i++){
            while (~pos && s[i] != s[pos+1]) pos = f[pos];
            if (s[i] == s[pos+1]) pos++;
            f[i] = pos;
            while (~pos){
                ans++;
                pos = f[pos];
            }
            pos = f[i];
        }
        ans += n;
        ans %= 10007;
        cout << ans << "\n";
    }
}