洛谷P3449 PAL Palindromes

2022-09-23 07:07:06 字數 1486 閱讀 9906

不難發現,一個長度較短的串\(s1\)與長度較長的串\(s2\)拼接起來能是一個迴文串,必須滿足以下兩點:

\(s1\)是將\(s2\)顛倒過來的串\(s2'\)的字首。

設\(s1\)長度為\(len1\),\(s2'\)長度為\(len2\),那麼\(s2'\)的\([len1+1,len2]\)所構成的子串必須是一個迴文串,其實也就是\(s2\)的\([1,len2-len1]\)必須是迴文串。

那麼我們把所有的串用\(vector\)存起來,然後全部插入一棵\(trie\)裡,再列舉每一個串,將它倒過來在\(trie\)裡尋找。

如果找到某一個時刻有一個串與這個倒過來的串相匹配,那麼說明這兩個串滿足了條件\((1)\)。如果再滿足剩餘部分是一個迴文串,那麼這兩個串就對答案有貢獻。

判斷是否是迴文串用\(hash\)就可以了。正序做一遍\(hash\),倒序做一遍\(hash\),然後判斷一個區間是否迴文就把這個區間的前半部分的正序\(hash\)值與後半部分的倒序\(hash\)值相比較即可。

由於這道題給出的串全部迴文,所以每一個可行方案倒過來也是一種可行方案,所以\(ans\)要乘\(2\),又因為我們沒有計算自己與自己匹配,所以最終答案是\(2ans+n\)。

時間複雜度\(o(n)\)

\(update:\)其實可以不用倒過來的。。。因為給出的串都是迴文串,倒過來的字首其實還是原來的字首。。。當時傻掉了。

#include #include #include #include #include #include using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int n=2000010;

const ull base=131;

int n,maxn,len[n];

ll ans;

char ch;

ull hash[n][3],power[n];

vectorch;

string s;

struct trie

if (trie[p][ch[i][j]-'a'+1]) p=trie[p][ch[i][j]-'a'+1];

else return;

} }void update(int i)

ch.push_back(s);

maxn=max(maxn,len[i]);

} power[0]=1;

for (register int i=1;i<=maxn;i++)

power[i]=power[i-1]*base;

trie.tot=1;

for (register int i=1;i<=n;i++)

trie.update(i);

for (int i=1;i<=n;i++)

printf("%lld\n",ans*2+n);

return 0;

}