[The Problem to Slow Down You]接尾辞自動機+マラ車の作り方

5379 ワード
ざっくりした
リンクのG題:  http://codeforces.com/gym/100548                                 
1.回文樹ができないので、タイトルを見るとSAM
2.よく考えてみると、SAMの1つのノードが表す文字列は、せいぜい1つだけが回文列であることがわかります.
同じアルファベットで終わる異なる文字列が現れる位置が完全に同じとは限らない.
長さnのシリアル種が現れる回文サブシリアル種がn種を超えないことを説明する
3.ノードに格納されている文字列に文字列があるかどうか、新しいノードを作成するときにどのように判断しますか?
もしあるならば、必然的に現在の文字で終わる最も長いその回文列です
Manacherは最長の長さを処理します.それからminlen[cur]以上かどうかを比較すればいいです.
4.SAMの前のノードに一致する場合、具体的にどのくらい追加しますか?
現在一致する文字列の長さをlenと仮定
それはlenより短い文列がパターン列に現れる回数を加える.
具体的にはsuffix_linkは探しに行って、その出現の回数に乗ることを覚えています
5.ついでに振り返ってみると、回文樹でできるような、SAM+manacherでもできる?
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define pr(x) cout << #x << " = " << x << endl;
#define bug cout << "bugbug" << endl;
#define ppr(x, y) printf("(%d, %d)
", x, y);
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define SQR(a) ((a)*(a))
#define PCUT puts("
---------------")

typedef long long ll;
typedef double DBL;
typedef pair P;
typedef unsigned int uint;
const int MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 4e5 + 4;
const int maxm = 1e3 + 4;
const double pi = acos(-1.0);


int m[maxn], M[maxn], Temp[maxn];
char buf[maxn];
void manacher(char* s){
	int j = 1;
	buf[0] = '#';
	for (int i = 0; s[i]; ++i){
		buf[j++] = '$';
		buf[j++] = s[i];
	}
	buf[j++] = '$';
	buf[j++] = 0;
	int center = -1, maxv = -1;
	for (int i = 1; buf[i]; ++i){
		m[i] = i <= maxv ? min(m[2*center-i], maxv - i + 1) : 1;
		while(buf[i-m[i]] == buf[i+m[i]]) m[i]++;
		if (i + m[i] - 1 > maxv){
			maxv = i + m[i] - 1;
			center = i;
		}
	}
	int lst = 0;
	for (int i = 1; buf[i]; ++i)
		if (i + m[i] - 1 > lst) while (i + m[i] - 1 > lst){
			lst++;
			Temp[lst] = (lst - i) * 2 + 1;
		}
	
	for (int i = 2; buf[i]; i += 2){
		M[i/2-1] = (Temp[i] + 1) / 2;
	}
	return;
} 
stack sta;
struct SuffixAutoMachine{
	int trans[maxn][26], maxlen[maxn], link[maxn], cnt, lst;//      AC          
	int times[maxn], in[maxn];
	ll plus[maxn], len_p[maxn];//           
	inline int id(char x){
		return x - 'a';
	}
	void newNode(){
		cnt++;
		memset(trans[cnt], -1, sizeof trans[cnt]);
		link[cnt] = len_p[cnt] = -1;
		times[cnt] = plus[cnt] = 0;
		return; 
	}
	void insert(int id){
		newNode();
		maxlen[cnt] = maxlen[lst] + 1;
		times[cnt] = 1; 
		int u = lst;
		while(u != -1 && trans[u][id] == -1){
			trans[u][id] = cnt;
			u = link[u];
		} 
		if (u == -1){
			link[cnt] = 0;
			lst = cnt;
			return;
		}
		int q = trans[u][id];
		if (maxlen[q] == maxlen[u] + 1){
			link[cnt] = q;
			lst = cnt;
			return;
		}
		int cur = cnt, sq = cnt+1;
		newNode();
		maxlen[sq] = maxlen[u] + 1;
		memcpy(trans[sq], trans[q], sizeof trans[q]);
		link[sq] = link[q];
		link[q] = sq;
		link[cur] = sq;
		lst = cur;
		if (len_p[q] != -1 && len_p[q] <= maxlen[sq]){
			len_p[sq] = len_p[q];
			len_p[q] = -1;
		}
		while(u != -1 && trans[u][id] == q){
			trans[u][id] = sq;
			u = link[u];
		}
		return;
	}
	void init(){
		cnt = -1;
		newNode();
		maxlen[0] = 0;
		lst = 0;
		
	}
	void construct(char* s){
		init();
		for (int i = 0; s[i]; ++i){
			insert(id(s[i]));
			int bef = link[lst];
//			cout << s[i] << ' ' << M[i] << ' ' << maxlen[bef] << endl;
			if (M[i] > maxlen[bef]) len_p[lst] = M[i];
		}
		while(sta.size()) sta.pop();
		memset(in, 0, sizeof in);			
		for (int i = 1; i <= cnt; ++i) in[link[i]]++;
		queue q;
		for (int i = 1; i <= cnt; ++i) if (!in[i]) q.push(i);
		while(q.size()){
			int top = q.front(); q.pop(); sta.push(top);
			if (top == 0) continue;
			times[link[top]] += times[top];
			if (--in[link[top]] == 0) q.push(link[top]);
		} 
		while(sta.size()){
			int top = sta.top(); sta.pop();
			if (top == 0) continue;
			plus[top] = plus[link[top]];
			if (len_p[top] != -1) plus[top] += times[top];
		}
		
	}
	ll match(char *s){
		ll sum = 0;
		int cur = 0, len = 0;
		for (int i = 0; s[i]; ++i){
			int j = id(s[i]);
			while(cur && trans[cur][j] == -1) cur = link[cur], len = maxlen[cur];
			if (trans[cur][j] != -1){
				cur = trans[cur][j];
//				cout << i << ' ' << maxlen[cur] << ' ' << plus[cur] << endl;
				len++;
//				cout << len_p[cur] << endl;
				if (len_p[cur] != -1 && len_p[cur] <= len) sum += plus[cur];
				else sum += plus[link[cur]];
			}
		}
		return sum;
	}
}SAM;


char a[maxn], b[maxn];
int main(){
//        
	int ik, i, j, k, kase;
	//SAM             。 
	//    --i   cur == 0          
	scanf("%d", &kase);
	for (ik = 1; ik <= kase; ++ik){
		scanf("%s%s", a, b);
		manacher(a);
		SAM.construct(a);
		printf("Case #%d: %I64d
", ik, SAM.match(b));
	}
	return 0;
}
/*
10
ewewewwe
eeewwwwq
ewewewwe
eee
*/
Notification用法復習(3.0以降)
ios解析jsonファイルtouchjsonを使用して解析