字符串学习笔记

相关概念

对于字符串$ S $,其前缀为$ pre(s,r) = s[0…r] $,后缀为$ suf(s,r) = s[|s| - r - 1 …..|s|] $，其中$ 0 < r < |s| $
如果对于字符串有$ pre(s,r) = suf(s,r) $，则称$ pre(s,r) $是该字符串的$ border $,此时可以得到字符串的一个周期为$ |s| - r $

相关算法及数据结构

KMP算法

对于模式串和匹配串
在一个字符串中匹配另外一个字符串的时候，如果一位一位的匹配，在发现某个字符不一样的时候将匹配串进行右移进行匹配，算法的效率是十分低下的，这个时候可以考虑在匹配失败的时候直接移动到匹配失败的位置
那么就需要求一个$ next $数组，即字符串在该位置已匹配的字符数量‘
$ next $数组是当前位置之前的字符串字串前缀与后缀的最大长度

求一个字符串的next数组，需要将其本身作为匹配串，从第2位开始匹配，这里令$ nest[0] = 0 $，然后依次匹配求出该数组

char s[len];
int next[len];
void GetNext()
{
    int i = 0,j = 1;
    next[0] = -1;
    while(i < strlen(s)){
        if(j == -1||s[i] = s[j]){
            i++;
            j++;
            next[i] = j;
        }
        else j = next[j];
    }
}

后缀数组及Height数组

先存个代码。。理解了再写（
后缀数组（SA），表示一个字符串中，后缀排第几名（rank）的后缀$ (suf(s,i)) $在第几个位置

后缀数组的倍增+基数排序求法，时间复杂度$ O(nlogn) $
暂时当个板子用（实在无法理解

char s[N];

int r[N],sa[N],x[N],y[N],p,m = 150;

bool cmp(int *r,int x,int y,int l){return r[x] == r[y] && r[x + l] == r[y + l]; }

int main(){
	cin>>s;
	int len = strlen(s);
	for(int i = 0;i<m;i++) r[i] = 0;
	for(int i = 0;i<len;i++) r[x[i] = s[i]] ++;
	for(int i = 0;i<m;i++) r[i] += r[i-1];
	for(int i = len - 1;i>=0;i--) sa[--r[x[i]]] = i;
	for(int j = 1,p = 1;j<=len;j<<=1,m = p){
		p = 0;
		for(int i = len - j;i<len;i++) y[p++] = i;
		for(int i = 0;i<len;i++) if(sa[i] >= j) y[p++] = sa[i] - j;
		for(int i = 0;i<=m;i++) r[i] = 0;
		for(int i = 0;i<len;i++) r[x[i]] ++;
		for(int i = 0;i<=m;i++) r[i] += r[i-1];
		for(int i = len - 1;i>=0;i--) sa[--r[x[y[i]]]] = y[i];
		swap(x,y);
	    p = 1;
	    x[sa[0]] = 0;
	    for(int i = 1;i<len;i++) x[sa[i]] = cmp(y,sa[i - 1],sa[i],j)?p-1:p++;
	}
    return 0;
}

利用后缀数组求Height数组
$ Height[i] $表示的是后缀$ sa[i - 1] $与后缀$ sa[i] $的最长公共前缀的长度
Height数组表征的是后缀的公共前缀的长度，那么由sa数组的性质可以知道:

$ Height[i] >= Height[i-1] - 1 $ 利用该性质可以从前往后求出Height数组

void GetHeight(char *s,int *sa,int *h){
    int rank[N];
    int j,k = 0;
    for(int i = 1;i<=n;i++) rank[sa[i]] = i;    //后缀数组与名次数组的逆运算性质
    for(int i = 0;i<n;i++,h[rank[i++]] = k)
    for(k?k--:0,j = sa[rank[i] - 1];s[i+k] == s[j+k];k++);
    return ;
}

后缀自动机

(待填坑….)

Trie树

Trie树又被称为字典树
因为在Trie树上查询字符串类似于查询字典的操作
在每个结点储存一个字符，然后构造树可以用于删除，查询，插入等操作

用结构体定义一个Trie树结点，一个结点包含一个布尔类型和接下去的结点的数组

struct Node{
    bool isStr;
    Node* Next[Num];
};

这里仅仅给出插入操作的方法，其他具体操作可见我原来CSDN博客里面的Trie树模板

void insert(Node* root,const char* word){
    Node* now = root;
    while(*word){
        if(now->Next[word - 'a'] == NULL){
            Node *newnode = new Node();
            newnode->isStr = false;
            memset(newnode->Next,NULL,memset(newnode->Next));
            now -> Next[word - 'a'] = newnode;
        }
        now = *newnode;
        word++;
    }
    now -> isStr = ture;
}

AC自动机

目前我只能记得的是KMP+Trie树(待填坑….)
AC自动机（Aho-Corasick automaton）是利用Trie树的结构，KMP的思修构造的有限状态自动机

有限状态自动机（FSM “finite state machine” 或者FSA “finite state automaton” ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。

所以对于AC自动机的构建，在于fail指针的构造，其结点与Trie树相比多保存了fail指针，指向失配后跳转的位置
其实其失配指针指向的位置表示的是在树的其他某个结点开始的前缀与当前匹配了的位置，然后继续匹配
所以利用循环的方式在构造的时候只要没查询到fail指向root
那么就继续查询fail指针指向的fail指针的位置，直到最后查询的fail指针的子节点存在与当前失配的位置所对应的字符

在构造trie树之后，bfs遍历构造fail指针：

1、对于当前的结点，先检查一下结点下面的某个字符是否存在
2、如果存在的话，就获取当前结点的fail指针
3、然后查询该fail指针下面的对应字符是否存在

不存在，继续查询fail指针
存在，将子字符的fail指向当前结点的fail指针的对应字符的位置

直到找到这个fail指针下面的字符或者fail指针是指向根节点为止

struct acnode{
	acnode *child[26];
	int sum;
	acnode *fail;

};

void init(acnode *root){
	for(int i = 0;i<26;i++) root->child[i] = NULL;
	root->sum = 0;
	root->fail = NULL;
}

void insert(acnode *root,char *s){
	int len = strlen(s);
	acnode *t = root;
	for(int i = 0;i<len;i++){
		int pos = s[i] - 'a';
		if(t->child[pos] == NULL){
			acnode *newnode = new acnode;
			init(newnode);
			t->child[pos] = newnode;
			t = t->child[pos];
		}
		else{
			t = t->child[pos];
		}
	}
	t->sum++;
}

void getfail(acnode *root){
	queue<acnode*> q;
	for(int i = 0;i<26;i++){
		if(root->child[i] != NULL){
			root->child[i]->fail = root;
			q.push(root->child[i]);
		}
	}

	while(!q.empty()){
		acnode *now = q.front();
		q.pop();
		for(int i = 0;i<26;i++){
			if(now->child[i] != NULL){
				acnode *p;
				if(now == root){
					now->child[i]->fail = root;
				}
				else{
					p = now->fail;
				    while(p != NULL){
					    if(p->child[i] != NULL){
						    now->child[i]->fail = p->child[i];
						    break;
					    }
					    p = p->fail;
				    }
				    if(p == NULL) now->child[i]->fail = root;
				    q.push(now->child[i]);
				}

			}
		}
	}
}

int query(acnode *root,char *s){
	int cnt = 0;
	acnode *p = root;
	int len = strlen(s);
	for(int i = 0;i<len;i++){
		int pos = s[i] - 'a';
		while(p->child[pos] == NULL && p!= root) p = p->fail;
		p = p->child[pos];
		if(!p) p = root;
		acnode *now = p;
		while(now != root){
			if(now->sum >= 0){
				cnt += now->sum;
				now->sum = -1;
			}
			else break;
			now = now->fail;
		}
	}
	return cnt;
}

Manachar

Manachar算法又称为马拉车算法，是处理最长回文子串的一种算法
其复杂度最差为$O(n)$，如果是朴素算法，算法复杂度最大会是$O(n^2)$
该算法的主要思想是利用前面已经计算了的最长回文子串来对算法进行优化
对字符串进行预处理，依次插入字符串中没有出现过的字符
在处理每一个回文中心的时候，算出当前最大的回文半径右边的位置，然后在计算下一个回文半径的时候可以知道该回文中心相对于上一个回文中心的对称位置也应该是对称的，那么由此可以利用已经处理的回文半径来进行优化

假设最大的回文半径中心位置为mid
那么当当前处理的回文中心位置为i的时候，i在最大回文半径之内
根据回文串的性质可以知道以i为回文中心的回文串在相对mid对称的位置j，两个回文中心的回文串应该是一样的
所以可以得出当i小于最大回文半径位置的时候，有

$min(p[2*mid - 1],mx - i)$ p为当前下标对应位置的最大回文半径 然后为了保证在最大回文半径位置以外依然存在回文串，进行检测，然后更新最大回文半径

char s1[20000007],s2[20000007];
int p[20000007],id = 1,mx = 1,ans = -1;

int init(){
	s2[0] = '$';
	s2[1] = '#';
	int j = 2;
	int len = strlen(s1);
	for(int i = 0;i<len;i++){
		s2[j++] = s1[i];
		s2[j++] = '#';
	}
	s2[j] = '\0';
	return j;
}

int main(){
	memset(p,0,sizeof(p));
	cin>>s1;
	int len = init();
	for(int i = 1;i<len;i++){
		if(i < mx) p[i] = min(p[2 * id - 1],mx - i);
		else p[i] = 1;
		while(s2[i - p[i]] == s2[i + p[i]]){
			p[i] ++;
		}
		ans = max(ans,p[i] - 1);
		if(mx < i + p[i]){
			id = i;
			mx = i + p[i];
		}
	}
	cout<<ans<<endl;
	return 0;
}