Palindrome automaton

String Maintenance with iii as Tail Node

After adding a node

That is, in all the original true suffix palindrome strings (mark[fail[num]]mark[fail[num]]mark[fail[num]])

Add a palindrome string update (mark[num])

if (!tree[last][in[i] - 'a']) {
	/*operation*/
	mark[num] = mark[fail[num]] + 1;
    //Statistics the number of palindrome strings ending with this node
}
//Update last
cnt[i]=mark[last];

Palindrome Automata (PAM)

Interesting

Number of essentially different strings

That is, the number of nodes, throw out the number of nodes 1

mark[i]=num-1

Palindromes and Super Abilities

CA Loves Palindromic

Maintaining essentially different strings (information comes from subtrees)

For an essentially different string

His subtrees are accessible to him

Mark all strings and count all the subtree information.

Because the larger the number is, the deeper the number of layers is, the inverted traversal is enough.

for (int i = 1; i <= n; i++) {
	while (in[i - len[last] - 1] != in[i]) last = fail[last];
	if (!tree[last][in[i] - 'a']) {
		/*operation*/
	}
	last = tree[last][in[i] - 'a'];
	mark[last]++;	//Markup information
}
for (int i = num; i; i--) {
	mark[fail[i]] += mark[i];
    //Statistical subtree information
}

P3649 palindrome string

Cheerleading rehearsal

Maintain essentially different palindrome strings (information from fathers and ancestors)

Establishment of failfailfail tree

Using dfsdfs to retrospectively maintain the information of ancestors of backtext strings

void build() {
	memset(head, 0, sizeof(int) * (num + 1)); tot = 0;
	for (int i = 2; i <= num; i++) AddEdge(fail[i], i);
    //Build a tree with fail
}

int vis[maxn],res[maxn];
void dfs(int now) {
	vis[len[now]]++;//Maintaining ancestral information
    /*operation Statistical Answers*/
	for (int i = head[now]; i; i = edge[i].next)
		dfs(edge[i].v);	//dfs
	vis[len[now]]--;//To flash back
	return;
}

HDU6599 I Love Palindrome String

Palindromeness

Maintenance information has palindrome strings at both ends

Create two palindrome strings

One is being built, the other is being built upside down.

For i-node maintenance, I-node positive sequence palindrome string information and i+1-node reverse sequence palindrome string information can be merged.

struct PAM {
	int tree[maxn][26];
	int len[maxn], fail[maxn];
	int last, num , mark[maxn];
	void insert(char* in, int n) {
		/*operation*/
	}
}pre, suf;
int main() {
	scanf("%s", in + 1); in[0] = '#';
	int n = strlen(in + 1);
	pre.insert(in, n);
    //Positive Establishment
	reverse(in + 1, in + 1 + n);
	suf.insert(in, n);
    //Reverse Establishment
	int ans = 0;
	for (int i = 1; i < n; i++) {
		ans = max(ans, pre.mark[i] + suf.mark[n-i]);
        //Combination of two strings of information
	}
}

P4287 Double Palindrome

Harry and magic string

Front-end Add Node

pre, last tags added before and after maintenance

Take pre for example, when adding nodes

When the longest palindrome string after the new node is not itself, the newly added node will not affect the last one.

That is, len[last], fail[last]len[last], fail[last]len[last], fail[last] is correct.

When a new node is itself the longest palindrome string, it is necessary to update the last one.

The update method is to last=prelast=prelast=pre

Since only one side is counted, it is correct to count the number of different essential strings and the total number of strings.

But when maintaining other information, we need to think carefully.

The following inserts forward:

Backward insertion similar

void pre_insert(char* in, int i) {	//Forward Adding Method
	while (in[i + len[pre] + 1] != in[i]) pre = fail[pre];
	if (!tree[pre][in[i] - 'a']) {
		len[++num] = len[pre] + 2;
		int j = fail[pre];
		while (in[i + len[j] + 1] != in[i]) j = fail[j];
		fail[num] = tree[j][in[i] - 'a'];
		tree[pre][in[i] - 'a'] = num;
		mark[num] = mark[fail[num]] + 1;	//Number of Statistics
	}
	pre = tree[pre][in[i] - 'a'];
	if (len[pre] == stdr - stdl + 1) last = pre;//When it becomes a palindrome string, update last
	sum = sum + mark[pre];	//Total number of maintenance
}

Victor and String

Forward Star Optimized Space

When MLE, we can use chain forward star optimization

Creating a dictionary tree with a chain forward star

Query: Traverse all edges, because each point has limited access times in the dictionary tree, so the complexity will not exceed.

Assignment: that is, building a border

struct Edge{
	int v;
	int w;	//w is the value of the letter
	int next;
}edge[maxn];
int head[maxn], tot;
inline void AddEdge(int u, int v, int w) {
	edge[++tot].v = v;
	edge[tot].w = w;
	edge[tot].next = head[u];
	head[u] = tot;
}
int find(int now, int w) {	//Finding Functions
	for (int i = head[now]; i; i = edge[i].next)
		if (edge[i].w == w) return edge[i].v;
	return 0;
}
for (int i = 1; i <= n; i++) {
	while (in[i - len[last] - 1] != in[i]) last = fail[last];
	int treenode = find(last, in[i] - 'a');//Finding Nodes
	if (!treenode) {
		len[++num] = len[last] + 2;
		int j = fail[last];
		while (in[i - len[j] - 1] != in[i]) j = fail[j];
		fail[num] = find(j, in[i] - 'a');//Finding Nodes
		AddEdge(last, num, in[i] - 'a');//Build edge
		mark[num] = mark[fail[num]] + 1;
		treenode = num;	//Update node
	}
	last = treenode;
	cnt[i] = mark[last];
}

CF17E Palisection