Подпалиндромы
Problem's Link: http://informatics.mccme.ru//mod/statements/view.php?chapterid=1750#
Mean:
给你一个长度不超过1e5的字符串，要统计总共有多少个回文串。(第一次刷俄语题，还好有google翻译)。
analyse:
如果题目说是不同回文串的话，这题就是一个裸的回文树。
由于要求所有子串的回文数，所以我们在插入的时候还需要使用suffixLink往上走统计答案。
Time complexity: O(N)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-17-19.13
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN = 105000;
struct node
{
int next [ 26 ];
int len;
int sufflink;
int num;
};
int len;
char s [ MAXN ];
node tree [ MAXN ];
int num; // node 1 - root with len -1, node 2 - root with len 0
int suff; // max suffix palindrome
long long ans;
bool addLetter( int pos)
{
int cur = suff , curlen = 0;
int let = s [ pos ] - 'a';
while( true)
{
curlen = tree [ cur ]. len;
if( pos - 1 - curlen >= 0 &&s [ pos - 1 - curlen ] ==s [ pos ]) break;
cur = tree [ cur ]. sufflink;
}
if( tree [ cur ]. next [ let ])
{
suff = tree [ cur ]. next [ let ];
return false;
} suff = ++ num;
tree [ num ]. len = tree [ cur ]. len + 2;
tree [ cur ]. next [ let ] = num;
if( tree [ num ]. len == 1)
{
tree [ num ]. sufflink = 2;
tree [ num ]. num = 1;
return true;
}
while( true)
{
cur = tree [ cur ]. sufflink;
curlen = tree [ cur ]. len;
if( pos - 1 - curlen >= 0 && s [ pos - 1 - curlen ] == s [ pos ])
{
tree [ num ]. sufflink = tree [ cur ]. next [ let ];
break;
}
}
tree [ num ]. num = 1 + tree [ tree [ num ]. sufflink ]. num;
return true;
}
void initTree()
{
num = 2; suff = 2;
tree [ 1 ]. len = - 1; tree [ 1 ]. sufflink = 1;
tree [ 2 ]. len = 0; tree [ 2 ]. sufflink = 1;
}
int main()
{
gets(s);
initTree();
for( int i = 0;s [ i ]; i ++)
{
addLetter( i);
ans += tree [ suff ]. num;
} cout << ans << endl;
return 0;
}
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-17-19.13
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN = 105000;
struct node
{
int next [ 26 ];
int len;
int sufflink;
int num;
};
int len;
char s [ MAXN ];
node tree [ MAXN ];
int num; // node 1 - root with len -1, node 2 - root with len 0
int suff; // max suffix palindrome
long long ans;
bool addLetter( int pos)
{
int cur = suff , curlen = 0;
int let = s [ pos ] - 'a';
while( true)
{
curlen = tree [ cur ]. len;
if( pos - 1 - curlen >= 0 &&s [ pos - 1 - curlen ] ==s [ pos ]) break;
cur = tree [ cur ]. sufflink;
}
if( tree [ cur ]. next [ let ])
{
suff = tree [ cur ]. next [ let ];
return false;
} suff = ++ num;
tree [ num ]. len = tree [ cur ]. len + 2;
tree [ cur ]. next [ let ] = num;
if( tree [ num ]. len == 1)
{
tree [ num ]. sufflink = 2;
tree [ num ]. num = 1;
return true;
}
while( true)
{
cur = tree [ cur ]. sufflink;
curlen = tree [ cur ]. len;
if( pos - 1 - curlen >= 0 && s [ pos - 1 - curlen ] == s [ pos ])
{
tree [ num ]. sufflink = tree [ cur ]. next [ let ];
break;
}
}
tree [ num ]. num = 1 + tree [ tree [ num ]. sufflink ]. num;
return true;
}
void initTree()
{
num = 2; suff = 2;
tree [ 1 ]. len = - 1; tree [ 1 ]. sufflink = 1;
tree [ 2 ]. len = 0; tree [ 2 ]. sufflink = 1;
}
int main()
{
gets(s);
initTree();
for( int i = 0;s [ i ]; i ++)
{
addLetter( i);
ans += tree [ suff ]. num;
} cout << ans << endl;
return 0;
}
