2022 年牛客多校第九场 G 题题解

G Magic Spells

题意：给定 $kk$ 个串 $\{S_i\}\backslash \{S\_i\backslash \}$，问在每个串中都出现的本质不同回文子串个数。$\sum \mathrm{\mid }{S}_i\mathrm{\mid }\le 3\times 10^5\backslash sum|S\_i|\; \backslash leq\; 3\backslash times\; 10^5$，$k\le 5k\; \backslash leq\; 5$。

解法：$kk$ 较小，因而可以考虑对每个串都建立一个 PAM，然后同时对 $kk$ 个 PAM 进行遍历，只向每个 PAM 都能扩展出来的字符出边走。整体时间复杂度 $\mathcal{O}(k\mathrm{\mid }{S}_i\mathrm{\mid })\backslash mathcal\; O(k|S\_i|)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 300000;
class PAM
{
    
public:
	struct node
	{
		int ch[26];
		int fail;
		int len;
        int cnt;
        node ()
		{
			memset(ch, 0, sizeof(ch));
			fail = len = cnt = 0;
		}
	} NIL;
	vector<node> t;
	int tot, len, last;
	string s;
    int getfail(int x, int place)
    {
		while (s[place - t[x].len - 1] != s[place])
			x = t[x].fail;
		return x;
	}
	PAM()
    {
        s = " ";
        tot = 1;
        t.push_back(NIL);
        t.push_back(NIL);
        t[0].len = 0;
		t[0].fail = 1;
		t[1].len = -1;
        last = 0;
    }
    int insert(int ch, int ind)
	{
        s += ch;
        int p = getfail(last, ind);
        if (!t[p].ch[ch])
        {
            int q = ++tot;
            t.push_back(NIL);
            t[q].len = t[p].len + 2;
            t[q].fail = t[getfail(t[p].fail, ind)].ch[ch];
            t[p].ch[ch] = q;
            t[q].cnt = t[t[q].fail].cnt + 1;
        }
		last = t[p].ch[ch];
        return t[last].cnt;
    }
} t[5];
string s[5];
long long cnt;
int k;
void dfs(vector<int> p)
{
    if(t[0].t[p[0]].len >= 1)
        cnt++;
    for (int i = 0; i < 26;i++)
    {
        auto temp = p;
        bool flag = 1;
        for (int j = 0; j < k;j++)
            if (!t[j].t[p[j]].ch[i])
            {
                flag = 0;
                break;
            }
        if(flag)
        {
            for (int j = 0; j < k;j++)
                temp[j] = t[j].t[p[j]].ch[i];
            dfs(temp);
        }
    }
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> k;
    for (int i = 0; i < k;i++)
    {
        cin >> s[i];
        int ind = 0;
        for (auto j : s[i])
            t[i].insert(j - 97, ++ind);
    }
    vector<int> pos1(k, 1), pos0(k, 0);
    dfs(pos1);
    dfs(pos0);
    cout << cnt;
    return 0;
}