P5546公共串

Hash + 二分 $O(n^2logn)$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int P = 29, MOD = 1e9 + 7, N = 2005;
int n, l = 1, r = 2005, ans = 0;
int powP[N], a[6][N];
string s[6];
inline int cal(int x, int l, int r)
{
    return (a[x][r] - a[x][l - 1] * powP[r - l + 1] % MOD + MOD) % MOD;
}
inline bool check(int x)
{
    for (int i = 1; i + x - 1 <= s[1].size() - 1; i++) //枚举s[1]中每一个长度为x的字串
    {
        int now = cal(1, i, i + x - 1), cnt = 1;
        for (int j = 2; j <= n; j++) // 分别在其他单词中查找    
        {
            bool flag = false;
            for (int k = 1; k + x - 1 <= s[j].size() - 1; k++) // 枚举s[i]中每一个长度为x的字串
            {
                if (now == cal(j, k, k + x - 1))
                {
                    flag = true;
                    cnt++;
                    break;
                }
            }
            if (!flag)
                break;
        }
        if (cnt == n)
            return true;
    }
    return false;
}
inline void init(int x, int len)
{
    powP[0] = 1;
    for (int i = 1; i <= len; i++)
    {
        a[x][i] = (a[x][i - 1] * P + s[x][i] - 'a' + 1) % MOD;
        powP[i] = powP[i - 1] * P % MOD;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        int len = s[i].size();
        r = min(r, len);
        s[i] = "$" + s[i] + "^";
        init(i, len);
    }
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            l = mid + 1;
            ans = max(ans, mid);
        }
        else
            r = mid - 1;
    }
    cout << ans << endl;
}

字符串哈希【模板题】

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s[10005]; 

const int P1 = 31;
const int MOD1 = 1000000007;
int hash1[10005];

const int P2 = 29;
const int MOD2 = 998244353;
int hash2[10005];

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i];
	//生成每个字符串的哈希值
	for(int i=1;i<=n;i++){
		//s[i] -> hash[i]
		hash1[i] = 0;
		hash2[i] = 0;
		for(int j=0;j<s[i].size();j++)
		{
			hash1[i] = (hash1[i] * P1 + s[i][j])%MOD1;
			hash2[i] = (hash2[i] * P2 + s[i][j])%MOD2;
		}
	} 
	
	//暴力比较
	int ans = 0;
	for(int i=1;i<=n;i++)
	{
		bool flag = true;//初始认为 s[i] 没有出现过
		for(int j=1;j<i;j++)
		{
			if(hash1[i]==hash1[j]&&hash2[i]==hash2[j])
			{
				flag=false;
				break;
			}	
		}	
		if(flag)
			ans++;
	} 
	cout<<ans<<"\n";
	return 0;
}

优秀的拆分（95 分）

#include<bits/stdc++.h>
#define int long long 
using namespace std; 

const int P1 = 31;
const int MOD1 = 1000000007;
int P1_pow[2005];
int hash1[2005];

const int P2 = 29;
const int MOD2 = 998244353;
int P2_pow[2005];
int hash2[2005];

int t;
string s;

int getHash1(int l,int r){
	if(l==0)
		return hash1[r];
	return ((hash1[r] - hash1[l-1] * P1_pow[r-l+1] %MOD1) % MOD1 + MOD1) % MOD1;
}

int getHash2(int l,int r){
	if(l==0)
		return hash2[r];
	return ((hash2[r] - hash2[l-1] * P2_pow[r-l+1] %MOD2) % MOD2 + MOD2) % MOD2;
}

signed main()
{
	P1_pow[0] = 1;
	for(int i=1;i<=2000;i++)
		P1_pow[i] = P1_pow[i-1] * P1 % MOD1;
	P2_pow[0] = 1;
	for(int i=1;i<=2000;i++)
		P2_pow[i] = P2_pow[i-1] * P2 % MOD2;
	cin>>t;
	while(t--){
		cin>>s;
		for(int i=0;i<s.size();i++)
		{
			hash1[i] = hash1[i-1] * P1 + (s[i] - 'a' + 1);
			hash1[i] %= MOD1;
			hash2[i] = hash2[i-1] * P2 + (s[i] - 'a' + 1);
			hash2[i] %= MOD2;
		} 
		/*
		for(int i=0;i<s.size();i++)
			cout<<hash1[i]<<",";
		cout<<'\n';
		for(int i=0;i<s.size();i++)
			cout<<hash2[i]<<",";
		cout<<'\n';
		*/
		int ans = 0;
		for(int i=0;i<s.size();i++){
			//s[] ~ s[i] : AA
			//s[i+1]~ s[] : BB
			int cntAA = 0;
			int cntBB = 0;
			for(int Len = 1; Len <= (i+1)/2; Len++)
			{
				//cout<<i-Len+1<<"~"<<i<<":"<<i-Len-Len+1<<"~"<<i-Len<<"\n";
				//cout<<getHash1(i-Len+1,i)<<":"<<getHash1(i-Len-Len+1,i-Len)<<"\n";
				//cout<<getHash2(i-Len+1,i)<<":"<<getHash2(i-Len-Len+1,i-Len)<<"\n";
				// s[i-Len+1]~s[i] == s[i-Len-Len + 1]~ s[i - Len] 
				if(getHash1(i-Len+1,i) == getHash1(i-Len-Len+1,i-Len)&&
					getHash2(i-Len+1,i) == getHash2(i-Len-Len+1,i-Len))
					cntAA++;
			}
			for(int Len = 1; Len <= (s.size()-i)/2; Len++)
			{	
				// s[i+1]~s[i+Len] == s[i+Len+1]~ s[i+Len+Len+1] 
				//cout<<i+1<<"~"<<i+Len<<"::"<<i+Len+1<<"~"<<i+Len+Len<<"\n";
				//cout<<getHash1(i+1,i+Len)<<"::"<<getHash1(i+Len+1,i+Len+Len)<<"\n";
				//cout<<getHash2(i+1,i+Len)<<"::"<<getHash2(i+Len+1,i+Len+Len)<<"\n";
				if(getHash1(i+1,i+Len) == getHash1(i+Len+1,i+Len+Len)&&
					getHash2(i+1,i+Len) == getHash2(i+Len+1,i+Len+Len))
					cntBB++;
			}
			//cout<<i<<" "<<cntAA<<" "<<cntBB<<"\n";
			ans += cntAA * cntBB; 
		} 		
		cout<<ans<<"\n";
	}	
	return 0;
}

最长双回文串

#include <bits/stdc++.h>
using namespace std;
string tempS, s;
int P[112345 * 2];
// 以 i 开头的最长回文串
int f[112345 * 2];
// 以 i 结尾的最长回文串
int g[112345 * 2];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> tempS;
    s = "^";
    s += "#";
    for (int i = 0; i < tempS.length(); i++)
        s += tempS[i], s += "#";
    s += "$";
    int n = s.length();
    // manacher
    int C, R;
    C = R = 0;
    for (int i = 1; i < n - 1; i++)
    {
        int i_mirror = 2 * C - i; // C - i_mirror = i - C
        if (R > i)
            P[i] = min(R - i, P[i_mirror]);
        else
            P[i] = 0;
        while (s[i + P[i] + 1] == s[i - P[i] - 1])
            P[i]++;
        f[i - P[i]] = max(f[i - P[i]], P[i]);
        g[i + P[i]] = max(g[i + P[i]], P[i]);
        if (i + P[i] > R)
        {
            C = i;
            R = i + P[i];
        }
    }
    for (int i = 3; i <= n - 2; i++)
        f[i] = max(f[i], f[i - 2] - 2);
    for (int i = n - 4; i >= 1; i--)
        g[i] = max(g[i], g[i + 2] - 2);
    /*
    cout << s << endl;
    for (int i = 0; i < n; i++)
        cout << P[i];
    cout << endl;
    for (int i = 0; i < n; i++)
        cout << f[i];
    cout << endl;
    for (int i = 0; i < n; i++)
        cout << g[i];
    cout << endl;
    */
    int ans = 0;
    for (int i = 1; i <= n - 2; i++)
        if (s[i] == '#' && f[i] && g[i])
            ans = max(ans, f[i] + g[i]);
    cout << ans << "\n";
    return 0;
}

阅读理解

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
// hash
const ll MOD1 = 1000000007, MOD2 = 998244353;
const ll P1 = 29, P2 = 31;
pair<ll, ll> getHash(const string &s)
{
    ll hash1 = 0;
    ll hash2 = 0;
    for (int i = 0; i < s.length(); i++)
    {
        hash1 = (hash1 * P1 + s[i] - 'a' + 1) % MOD1;
        hash2 = (hash2 * P2 + s[i] - 'a' + 1) % MOD2;
    }
    return make_pair(hash1, hash2);
}
set<pair<ll, ll>> se[1005];
string tempS;
pair<ll, ll> pll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int k;
        cin >> k;
        while (k--)
        {
            cin >> tempS;
            se[i].insert(getHash(tempS));
        }
    }
    cin >> m;
    while (m--)
    {
        cin >> tempS;
        pll = getHash(tempS);
        for (int i = 1; i <= n; i++)
            if (se[i].find(pll) != se[i].end())
                cout << i << " ";
        cout << "\n";
    }
    return 0;
}

manecher

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 11000000 * 2 + 3;
int n, P[MAXN+5];
string tempS, s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> tempS;
    //build
    s += "^", s += "#";
    for (int i = 0; i < tempS.length(); i++)
        s += tempS[i], s += "#";
    s += "$";
    n = s.length();
    //manacher
    int C, R;
    C = R = 0;
    for (int i = 1; i < n - 1; i++)
    {
        int i_mirror = 2 * C - i; //C - i_mirror = i - C
        if (R > i)
            P[i] = min(R - i, P[i_mirror]);
        else
            P[i] = 0;
        while (s[i + P[i] + 1] == s[i - P[i] - 1])
        {
            P[i]++;
        }
        if (i + P[i] > R)
        {
            C = i;
            R = i + P[i];
        }
    }
    //ans
    int ans = 0;
    for (int i = 1; i < n; i++)
        ans = max(ans, P[i]);
    cout << ans << endl;
    return 0;
}