anacher

马拉车算法就是求解最长回文串

并且将时间复杂度降到了O（n），

它的原理就是将原始字符串进行了处理，在每一个字符的左右两边都加上特殊字符，让字符串变成一个奇回文

然后通过数组储存标记，详细看这篇

回文自动机

回文树，也叫回文自动机

类似AC自动机的一种回文串匹配自动机，也就是一棵字符树。同样类似AC自动机的是，每一个节点都有一个fail指针，fail指针指向的点表示当前串后缀中的最长回文串。

 

 

Now, you are given a string S. We want to know how many distinct substring of S which is palindrome.

InputThe first line of the input contains a single integer T(T<=20), which indicates number of test cases.

Each test case consists of a string S, whose length is less than 100000 and only contains lowercase letters.

OutputFor every test case, you should output "Case #k:" first in a single line, where k indicates the case number and starts at 1. Then output the number of distinct substring of S which is palindrome.

Sample Input

3aaaaabababcd

Sample Output

Case #1: 4Case #2: 4Case #3: 4

因为回文自动机中每个新建的结点就表示一个回文子串，各个结点都不相同

所以不同回文子串个数就是回文自动机中新增结点个数，直接输出即可

#include
     
      using namespace std;const int maxn=100010;const int ma=26;typedef long long ll;struct node{    int next[maxn][ma];//和字典树的next指针类似     int fail[maxn];//失配后指向fail指针     ll cnt[maxn];    int num[maxn];    int len[maxn];//回文串长度     int s[maxn];//字符     int last;    int n,p;//添加的字符个数，节点个数    int newnode(int l)    {        for(int i=0;i
      
       =0;i--)          cnt[fail[i]]+=cnt[i];    }}tree;int main(){    string a;    std::ios::sync_with_stdio(false);    int t;    int m=1;    cin>>t;    while(t--)    {        cin>>a;        tree.init();        int len=a.size();        for(int i=0;i