Palindrome Mouse
题意:若把给定字符串的所有不同回文子串放到一个集合内,求集合内有多少对回文子串满足其中一个是另一个的子串。
思路:
- 建好回文自动机
- 若设 ansi为回文树上能到达 i节点的节点数( 0,1除外),则题目要求的就是 i=2∑szansi
- 那么如何统计能到达某个节点的节点数呢?我们采用 DFS的方法,一边沿着 ch边跑,一边沿着 fail边跑,并且将跑过的边打上标记,离开 DFS的时候删除标记(用vector记录哪些点是刚刚打过标记的)
- 然后,在每个节点处都累加答案即可
题目描述
Doctor has a string s consisting of only lowercase letters. Doctor has got the set of all palindromic substrings of a string s, denoted by the set S. Now, he wants to choose two distinct strings a and b from the set S which satisfy that the string a is a substring of the string b. How many different pairs (a, b) can Doctor choose?
输入描述:
There are multiple test cases. The first line contains an integer T (1≤T≤5), indicating the number of test cases. Test cases are given in the following.
Each test case consists of only one line, containing a non-empty string s (1≤∣s∣≤100000), consisting of only lowercase letters.
输出描述:
For each test case, output “Case #x: y” in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.
示例
输入
4
aaaa
abba
abacaba
abc
输出
Case #1: 6
Case #2: 4
Case #3: 14
Case #4: 0
//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;
char s[maxn];
int ch[maxn][26], fail[maxn], len[maxn], cnt[maxn];
bool vis[maxn];
int last, sz, pos;
ll ans, res;
void init() {
for(int i=0; i<=sz; ++i) {
for(int j=0; j<26; ++j) ch[i][j]=0;
}
fail[0]=fail[1]=last=sz=1;
len[1]=pos=-1;
ans=0;
}
void add(int c) {
++pos; int p=last;
while(s[pos-len[p]-1]!=s[pos]) p=fail[p];
if(!ch[p][c]) {
int np=++sz, fp=fail[p];
len[np]=len[p]+2;
while(s[pos-len[fp]-1]!=s[pos]) fp=fail[fp];
fail[np]=ch[fp][c];
ch[p][c]=np;
}
last=ch[p][c];
}
void dfs(int u) {
vector<int> v;
for(int i=u; i>1&&!vis[i]; i=fail[i]) vis[i]=1, res++, v.pb(i);
ans+=u>1?res-1:0;
for(int i=0; i<26; ++i) if(ch[u][i]) dfs(ch[u][i]);
for(auto p: v) vis[p]=0, res--;
}
int main() {
//ios::sync_with_stdio(false);
int T=read();
int t=0;
while(T--) {
scanf("%s", s);
init();
for(int i=0; s[i]; ++i) add(s[i]-'a');
dfs(0), dfs(1);
printf("Case #%d: %lld\n", ++t, ans);
}
}