精华内容
下载资源
问答
  • 将所给字符串存储起来 注意常数不能太大 使用扩展kmp计算反转串的每个后缀和原串的最长公公前缀 插入字典树时标记结束节点和当前位置为后缀是回文的节点 全部插入完毕后再匹配正向串 匹配时如果正向串下一个位置的...

    题解

    题目大意 n个字符串两两组合问拼起来的串有多少个回文串

    将所给字符串存储起来 注意常数不能太大 使用扩展kmp计算反转串的每个后缀和原串的最长公公前缀 插入字典树时标记结束节点和当前位置为后缀是回文的节点
    全部插入完毕后再匹配正向串 匹配时如果正向串下一个位置的后缀是回文串则加上当以当前节点结束的反转串数量 当正向串结束加上以当前节点结束的反向串和下一个位置后缀是回文的反向串

    AC代码

    #include <stdio.h>
    #include <iostream>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    
    const int INF = 0x3f3f3f3f;
    const int MAXN = 2e6 + 10;
    const int MAXC = 26;
    char s[MAXN], rev[MAXN];
    int exnex[MAXN]; //扩展next数组
    int exten[MAXN]; //s从i为起点的后缀与p的最长公共前缀
    int nex[MAXN][MAXC], sed[MAXN], idx; //每个字符连接的子节点编号 满足当前前缀的串数 以当前节点为结尾的串数 末尾节点
    int pla[MAXN];
    int len[MAXN]; //常数优化
    
    void getexnext(const char p[], int m)
    {
    	int i = 0, j;
    	exnex[0] = m; //0号位为长度
    	while (i + 1 < m && p[i] == p[i + 1]) //计算第一项
    		i++;
    	exnex[1] = i;
    	int k = 1 + i, po = 1; //k最远到达点 po最远到达点的起点
    	for (i = 2; i < m; i++)
    	{
    		if (exnex[i - po] < k - i) //因k~po == 0~k-po 则i~k == i-po~k-po(取前者后一部分)
    			exnex[i] = exnex[i - po]; //如果exnet[i-po]不足k-i长度则s[i - po + exnet[i-po]] != s[i + exnet[i-po]]
    		else
    		{
    			j = k - i;//如果长度相等或更长因k之后为未探索区域 暂定为k - i之后继续匹配
    			if (j < 0) //如果i本身就超过k
    				j = 0;
    			while (i + j < m && p[i + j] == p[j])
    				j++;
    			exnex[i] = j;
    			k = i + j, po = i; //更新记录
    		}
    	}
    }
    void exkmp(const char s[], const char p[], int n, int m)
    {
    	getexnext(p, m); //计算exnext
    	int i = 0, j;
    	while (s[i] == p[i] && i < m && i < n) //计算第零项
    		i++;
    	exten[0] = i;
    	int k = i, po = 0;
    	for (i = 1; i < n; i++) //从1开始计算
    	{
    		if (exnex[i - po] < k - i)
    			exten[i] = exnex[i - po]; //exten
    		else
    		{
    			j = k - i;
    			if (j < 0)
    				j = 0;
    			while (i + j < n && j < m && s[i + j] == p[j]) //n m s
    				j++;
    			exten[i] = j; //exten
    			k = i + j, po = i;
    		}
    	}
    }
    inline int GetID(char c)  //字符映射
    {
    	return c - 'a'; //简单的将字符减去'a' 根据需求改变
    }
    void Insert(char s[], int n) //字典树内插入一个字符串s长度为n
    {
    	int x = 0; //当前节点
    	for (int i = 0; i < n; i++) //串下标
    	{
    		int c = GetID(s[i]); //转换字符为id
    		if (!nex[x][c])
    			nex[x][c] = ++idx; //新增一个节点
    		if (exten[i] == n - i) //当前位置后缀为回文
    			pla[x]++; //前一个节点++
    		x = nex[x][c]; //移动节点
    	}
    	sed[x]++; //记录经过一次并记录在此处结束 
    }
    int Match(const char *s, int n)
    {
    	int x = 0;
    	int res = 0;
    	for (int i = 0; i < n; i++)
    	{
    		int c = GetID(s[i]);
    		if (exten[i] == n - i) //下一个位置的后缀是回文
    			res += sed[x]; //加在当前节点结束的数量
    		if (!nex[x][c]) //不存在节点
    		{
    			x = -1; //标记失配
    			break;
    		}
    		x = nex[x][c]; //移动节点
    	}
    	if (x != -1)
    		res += sed[x] + pla[x]; //已当前节点为结尾或下一个节点后缀为回文
    	return res;
    }
    
    int main()
    {
    #ifdef LOCAL
    	freopen("C:/input.txt", "r", stdin);
    #endif
    	int N;
    	cin >> N;
    	for (int i = 1; i <= N; i++)
    	{
    		int n;
    		scanf("%d%s", &n, s + len[i - 1]);
    		len[i] = len[i - 1] + n;
    		char *str = s + len[i - 1];
    		memcpy(rev, str, n); //拷贝指定长度的字符串
    		rev[n] = 0;
    		reverse(rev, rev + n);
    		getexnext(str, n); //反转串扩展kmp计算后缀是否为回文
    		exkmp(rev, str, n, n);
    		Insert(rev, n); //插入字典树并进行标记
    	}
    	ll ans = 0;
    	for (int i = 1; i <= N; i++) //插入完毕后在匹配
    	{
    		char *str = s + len[i - 1];
    		int n = len[i] - len[i - 1];
    		memcpy(rev, str, n);
    		rev[n] = 0;
    		reverse(rev, rev + n);
    		getexnext(rev, n); 
    		exkmp(str, rev, n, n);
    		ans += Match(str, n); //将每个字符串进行匹配
    	}
    	cout << ans << endl;
    
    	return 0;
    }
    
    展开全文
  • 字典树KMP

    2015-03-17 21:19:27
    字典树KMP的ppt课件 TJRAC_ACM内部使用
  • KMP字典树

    2020-07-26 08:57:40
    KMP 算法 概述 KMP 算法全称是 Knuth-Morris-Pratt 字符串查找算法,是用于在一个字符串(匹配串)中查找另一个字符串(模式串)的快速算法 KMP算法会在匹配前预处理模式串 PPP 得到 fail 数组, 借助 fail 数组,...

    KMP 算法

    概述

    KMP 算法全称是 Knuth-Morris-Pratt 字符串查找算法,是用于在一个字符串(匹配串)中查找另一个字符串(模式串)的快速算法

    KMP算法会在匹配前预处理模式串 P P P 得到 fail 数组, 借助 fail 数组,可以在匹配过程中减少很多冗余的操作,时间复杂度 : O ( n + m ) \mathcal{O}(n + m) O(n+m), 其中, n n n m m m 是两个串的长度

    算法流程

    fail 数组的预处理

    KMP 算法的核心是 fail 数组,对于字符串 s = s 0 , s 1 , s 2 , … , s n − 1 s = s_{0},s_{1},s_{2},\dots,s_{n - 1} s=s0,s1,s2,,sn1 ,如果 j j j 满足 s 0 … i = s i − j … i s_{0 \dots i} = s_{i - j \dots i} s0i=siji 的最大值,则 f a i l [ i ] = j fail[i] = j fail[i]=j 注意: j ≤ i j \le i ji 其中, s a … b s_{a \dots b} sab 表示字符串 s s s a a a 号位到 b b b 号位的子串

    对于不存在 s 0 … i = s i − j … i s_{0 \dots i} = s_{i - j \dots i} s0i=siji 的最大值,fail[i] = -1

    img

    对于字符串 “aababaab” 则 fail 值如下:

    img

    匹配过程

    img

    对于上面的过程,当 a? 比较时失败了,那么我们要把母串的起始位置移动到下一个位置,对于 2 2 2 指向的匹配,这时候我们没必要从头开始比较,因为我们知道 fail[i] = 1 如果红色块可以完美匹配,那么应该等于 4 4 4 , 第 3 3 3, 4 4 4 次也是同理,所以直接跳到匹配 %5%

    这就是 KMP 的本质:利用已经计算过了的信息加速匹配过程

    代码

    #include <iostream>
    #include <cstring>
    using namespace std;
    const int maxn = 100;
    int fail[maxn];
    void getFail(char *P) {
        int m = strlen(P);
        fail[0] = -1;
    	for (int i = 1; i < m; ++i) {
        	int j = fail[i - 1];
            while (j >= 0 && P[j + 1] != P[i]) {
                j = fail[j];
            }
            if (P[j + 1] == P[i]) {
                j++;
            }
            fail[i] = j;
        }
    }
    int KMP(char *T, char *P) {
        int n = strlen(T), m = strlen(P);
        int j = -1;
        for (int i = 0; i < n; ++i) {
            while (j >= 0 && P[j + 1] != T[i]) {
                j = fail[j];
            }
            if (P[j + 1] == T[i]) {
                j++;
                if (j + 1 == m) {
                    return i - m + 1;
                }
            }
        }
        return -1;
    }
    int main() {
        char s[maxn], t[maxn];
        cin >> s >> t;
        getFail(t);
        cout << KMP(s, t) << endl;
        return 0;
    }
    

    扩展 KMP 算法

    可以快速处理出字符串 S S S 的所有后缀和字符串 T T T 的最长公共前缀

    算法介绍

    next 函数

    next[i] 表示后缀 i i i T i … ∣ T ∣ T_{i \dots |T|} TiT T T T 的最长公共前缀

    例如:

    img

    注意 next 是基于模式串构建的

    假设 p = m a x ( i + n e x t [ i ] − 1 ) p = max(i + next[i] - 1) p=max(i+next[i]1) 对于所有 0 ≤ i ≤ x 0 \le i \le x 0ix 我们找到 i + n e x t [ i ] − 1 i + next[i] - 1 i+next[i]1 的最大值,令 k k k 为这个最大值对应的 i i i ,令 p p p k + n e x t [ k ] − 1 k + next[k] - 1 k+next[k]1 p p p 就是我们目前已知匹配到的最远位置

    我们可以得到 T k … p = T 0 … n e x t [ k ] − 1 T_{k \dots p} = T_{0 \dots next[k] - 1} Tkp=T0next[k]1 ,如下图所示蓝色部分:

    img

    可以得到 T x … p = T x − k … n e x t [ k ] − 1 T_{x \dots p} = T_{x - k \dots next[k] - 1} Txp=Txknext[k]1 (如下图红色部分)

    img

    l = n e x t [ x − k ] l = next[x - k] l=next[xk],根据下图,可以得到:

    T 0 … l − 1 = T x − k … x − l + l − 1 = T x … x + l − 1 T_{0 \dots l - 1} = T_{x - k \dots x - l + l - 1} = T_{x \dots x + l - 1} T0l1=Txkxl+l1=Txx+l1 (图中黄色部分)

    img

    也就是说,如果黄色部分小于红色部分的话,也就是 l < p − x + 1 l < p - x + 1 l<px+1 也即 x + l ≤ p x + l \leq p x+lp ,那么我们可以确定 n e x t [ x ] = l next[x] = l next[x]=l 否则,我们从 l + 1 l + 1 l+1 p + 1 p + 1 p+1 位置开始逐一比较,求出 n e x t [ i ] next[i] next[i] 的实际值

    解决原问题

    我们用 e x t e n d [ i ] extend[i] extend[i] 表示 S S S 的第 i i i 个后缀和 T T T 的最长公共前缀,假设 e x t e n d [ i ] ( 0 ≤ i < x ) extend[i] (0 \leq i < x) extend[i](0i<x) 的值已经求出,现在要计算 e x t e n d [ x ] extend[x] extend[x]

    已知 S k … p = T 1 … e x t e n d [ k ] S_{k \dots p} = T_{1 \dots extend[k]} Skp=T1extend[k], 求 S x … n S_{x \dots n} Sxn T 1 … m T_{1 \dots m} T1m 的最长公共前缀,与上面类似,记录 p = i + e x t e n d [ i ] − 1 p = i + extend[i] - 1 p=i+extend[i]1 的最大值.

    img

    根据红色部分的等价,我们可以利用 n e x t [ x − k ] next[x - k] next[xk] 得到黄色部分等价性,剩下的分析就和求 n e x t next next 的过程一样了。

    代码

    #include <iostream>
    #include <cstring>
    using namespace std;
    const int maxn = 100;
    int Next[maxn];
    void getNext(char *T) {
        int n = strlen(T);
        Next[0] = n;
        int p = 0;
        while (p + 1 < n && T[p] == T[p + 1]) {
            ++p;
        }
        Next[1] = p;
        int k = 1;
        for (int i = 2; i < n; ++i) {
            p = k + Next[k] - 1;
            int l = Next[i - k];
            if (i + l <= p) {
                Next[i] = l;
            } else {
                int j = p - i + 1;
                if (j < 0) {
                    j = 0;
                }
                while (i + j < n && T[i + j] == T[j]) {
                    j++;
                }
                Next[i] = j;
                k = i;
            }
        }
    }
    
    int extend[maxn];
    void getExtend(char *S, char *T) {
        int n = strlen(T), m = strlen(S);
        int p = 0;
        while (p < m && p < n && S[p] == T[p]) {
            p++;
        }
        extend[0] = p;
        
        int k = 0;
        for (int i = 1; i < m; ++i) {
            p = k + extend[k] - 1;
            int l = Next[i - k];
            if (i + l <= p) {
                extend[i] = l;
            } else {
                int j = p - i + 1;
                if (j < 0) {
                    j = 0;
                }
    			while (i + j < m && j < n && S[i + j] == T[j]) {
    				j++;
    			}
    
    			extend[i] = j;
    			k = i;
            }
        }
    }
    
    int main() {
        char S[maxn], T[maxn];
    	cin >> S >> T;
    	getNext(T);
    	getExtend(S, T);
    
    	int n = strlen(T), m = strlen(S);
    	for (int i = 0; i < n; ++i) {
    		cout << Next[i] << " " ;
    	}
    	cout << endl;
    
    	for (int i = 0; i < m; ++i) {
    		cout << extend[i] << " ";
    	}
        return 0;
    }
    

    Trie 树

    字典树,是利用字符串的公共前缀建立起的二叉树,可以支持插入,查询等操作,因查询时像查字典一样,从第一个字符遍历,所以得名字典树

    img

    字典树的性质

    img

    代码(模板):

    #include <iostream>
    #include <string.h>
    using namespace std;
    const int maxn = 10000;
    const int maxc = 26;
    struct Trie {
        int ch[maxn][maxc];
        int tot;
        int cnt[maxn];
        
        void init() {
            tot = 0;
            memset(cnt, 0, sizeof(cnt));
            memset(ch, -1, sizeof(ch));
        }
        
        void insert(char *str) {
            int p = 0;
            for (int i = 0; str[i]; ++i) {
                if (ch[p][str[i] - 'a'] == -1) {
                    ch[p][str[i] - 'a'] = ++tot;
                }
                p = ch[p][str[i] - 'a'];
            }
            cnt[p]++;
        }
        
        int find(char *str) {
            int p = 0;
            for (int i = 0; str[i]; ++i) {
                if (ch[p][str[i] - 'a'] == -1) {
                    return 0;
                }
                p = ch[p][str[i] - 'a'];
            }
            return cnt[p];
        }
        
        void erase(char *str) {
            int p = 0;
            for (int i = 0; str[i]; ++i) {
                if (ch[p][str[i] - 'a'] == -1) {
                    return;
                }
                p = ch[p][str[i] - 'a'];
            }
            if (cnt[p]) { // 是单词,不是前缀结点
    			--cnt[p];           
            }
        }
    };
    int main() {
        Trie name;
        name.init();
        name.insert("barty");
        name.insert("islands");
    	cout << name.find("islands") << endl;
        cout << name.find("bar") << endl;
        name.erase("islands");
        cout << name.find("islands") << endl;
        return 0;
    }
    

    字典树上的动态规划

    例题:

    img

    这个可以用 DP 解决,使用 f [ i ] f[i] f[i] 表示 T T T 前面 i i i 个长度的方案数:

    对于所有 j ( j < i ) j(j < i) j(j<i) 如果 T j … i T_{j \dots i} Tji 是一个单词,就有转移:
    d p [ i ] + = d p [ j − 1 ] dp[i] += dp[j - 1] dp[i]+=dp[j1]

    我们可以建立一颗字典树,然后令 T T T i i i 开始在字典树上查询。这样,当我们沿着字典树走到一个单词节点时,就相当于找到一个转移

    代码

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int maxn = 50000;
    const int maxc = 26;
    struct Trie {
      	char T[maxn];
        int ch[maxn][maxc];
        int tot;
        int cnt[maxn], dp[maxn];
        
        void init() {
            tot = 0;
            memset(cnt, 0, sizeof(cnt));
            memset(ch, -1, sizeof(ch));
            memset(dp, 0, sizeof(dp));
        }
        
        void insert(char *str) {
            int p = 0;
            for (int i = 0; str[i]; ++i) {
                if (ch[p][str[i] - 'a'] == -1) {
                    ch[p][str[i] - 'a'] = ++tot;
                }
                p = ch[p][str[i] - 'a'];
            }
            cnt[p]++;
        }
        
        void find(int st) {
            int p = 0;
            for (int i = st; T[i]; ++i) {
                if (ch[p][T[i] - 'a'] == -1) {
                    return ;
                }
                p = ch[p][T[i] - 'a'];
                if (cnt[p]) {
                    dp[i] += dp[st - 1];
                }
            }
        }
    };
    int main() {
        Trie word;
        word.init();
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            char s[110];
            cin >> s;
            word.insert(s);
        }
        
        scanf("%s", word.T + 1);
        
        word.dp[0] = 1;
        int i;
        for (i = 1; word.T[i]; ++i) {
            word.find(i);
        }
        cout << word.dp[i - 1] << endl;
        return 0;
    }
    
    展开全文
  • KMP字典树

    2020-08-23 17:01:01
    KMP 作用:字符串查找(在主串T中找模式串P) 关键:fail数组——充当失配函数,记录最长相同前缀和后缀长度 fail作用:已经有一段匹配上,但到某个字符匹配不上了,就可以直接到下一个有前面符合的字符的字符串开始...

    KMP
    作用:字符串查找(在主串T中找模式串P)
    关键:fail数组——充当失配函数,记录最长相同前缀和后缀长度
    fail作用:已经有一段匹配上,但到某个字符匹配不上了,就可以直接到下一个有前面符合的字符的字符串开始搜。(利用已知的信息加速匹配过程)
    时间:线性
    注意:fail记录的不是回文子串,是通过循环j(j<i),满足s0——j = si-j——i,不存在就为-1
    在这里插入图片描述

    实现:
    fail初始化-1
    跟着fail不断往下跳,匹配上就记录

    const int maxn = 100;
    int fail[maxn];
    void getFail(char *P){
    	int m=strlen(P);
        fail[0]=-1;
        for(int i=1;i< m;i++){
            int j=fail[i-1];
            while(j>=0 && P[j+1]!=P[i]){//P[i]和P[fail[i-1]+1]比较,沿着失配函数往前跳
                j=fail[j];
            }
            if(P[j+1]==P[i]){//跳出来,可能是满足匹配,也可能是跳出边界
    			j++;
            }
            fail[i]=j;
        }
    }
    int KMP(char *T,char *P){//T为主串,P为模式串
    	int n=strlen(T),m=strlen(P);
        int j=-1;//j记录当前匹配的长度
        for(int i=0;i<n;i++){
    		while(j>=0 && P[j+1]!=T[i]){//计算出最长匹配
                j=fail[j];
            }
            if(P[j+1]==T[i]){
                j++;
                if(j+1==m){
    				return i-m+1;//返回匹配的字符的第一个位置,m已经匹配上,故要+1
                }
            }
        }
        return -1;//这里是-1,0代表已经匹配成功
    }
    int main() {
        char s[maxn],t[maxn];
        cin>>s>>t;
        getFail(t);
        cout<<KMP(s,t)<<endl;
        return 0;
    }
    

    样例
    aabbabbba
    bba
    输出
    2

    拓展KMP:
    作用:处理出字符串S的所有后缀与字符串T的最长公共前缀(特殊的字符串的匹配问题)
    关键:next数组,记录自己的后缀和最长公共前缀
    next数组:T i——strlen(T)和T的最长公共前缀
    第一位等于字符串长度(自己和自己的最长公共前缀)
    在这里插入图片描述
    对这个样例,如第四位是a,那么它前面与以它为起始的的字符串最长的相同字符串就是0到2的aaa和4到6的aaa,长度为3,故next值为3
    在这里插入图片描述
    在这里插入图片描述
    extend[i]表示字符串S的第i个后缀和字符串T的最长公共前缀
    在这里插入图片描述

    const int maxn = 100;
    int Next[maxn];//库里有next
    void getNext(char *T){
        int n=strlen(T);
    	//初始化
        Next[0]=n;
        int p=0;
        while(p+1<n && T[p]==T[p+1]){
            ++p;
        }
        Next[1]=p;
        int k=1;//p最大的k等于1,不是0,因为0没包含任何匹配信息
        for(int i=2;i<n;i++){
    		p=k+Next[k]-1;
            int l=Next[i-k];
            if(i+l<=p){//黄色区域是否超过红色区域
    			Next[i]=l;
            }else{//往前走
                int j=p-i+1;
                if(j<0){//p-i+1可能会小于0,特殊处理
                    j=0;
                }
                while(i+j<n && T[i+j]==T[j]){//后面的部分还不知道是否匹配,继续暴力匹配
                    j++;
                }
                Next[i]=j;
                k=i;//这是k可以直接更新为i,因为i+Next[i]-1一定会超过之前的p
                
            }
        }
    }
    int extend[maxn];
    void getExtend(char *S,char *T){
        int n=strlen(T),m=strlen(S);
        int p=0;
        while(p<m && p<n && S[p]==T[p]){
            p++;
        }
         extend[0]=p;//暴力求出 
        int k=0;
        for(int i=1;i<m;i++){
    		p=k+extend[k]-1;
            int l=Next[i-k];
            if(i+l<=p){
                extend[i]=l;
            }else{
                int j=p-i+1;
                if(j<0){
    				j=0;
                }
                while(i+j<m && j<n && S[i+j]==T[j]){
                    j++;
                }
                extend[i]=j;
                k=i;
            }
        }
    }
    
    int main() {
        char S[maxn],T[maxn];
        cin>>S>>T;
        getNext(T);
        getExtend(S,T);
        int n=strlen(T),m=strlen(S);
        for(int i=0;i<n;i++){
    		cout<<Next[i]<<" ";
        }
        cout<<endl;
        for(int i=0;i<m;i++){
    		cout<<extend[i]<<" ";
        }
        return 0;
    }
    

    总结:求fail,next,extend数组都是用拓展的思想

    字典树
    字符串公共前缀
    支持字符串插入,查询操作,用于大量字符串的检索,去重,排序操作
    常用来处理有关字符串概率的问题:
    类似乘法原理,前面公共的部分被多条路走过,就是乘
    也可以用来优化:
    存储0和1
    特点:
    在这里插入图片描述
    实现:
    cnt数组记录是否是一个单词
    tot记录节点数

    const int maxn=10000;
    const int maxc=26;
    struct Trie {
        int ch[maxn][maxc];//每个节点的26个可能的子节点编号 
        int tot;//当前节点数量
        int cnt[maxn];
        void init(){
            tot=0;
            memset(cnt,0,sizeof(cnt));
            memset(ch,-1,sizeof(ch));
        }
        void insert(char *str){//插入
            int p=0;
            for(int i=0;str[i];i++){
                if(ch[p][str[i]-'a']==-1){//该节点不存在
                    ch[p][str[i]-'a']=++tot;
                }
                p=ch[p][str[i]-'a'];//继续插入
            }
            cnt[p]++;
        }
        int find(char *str){
            int p=0;
            for(int i=0;str[i];i++){
    			if(ch[p][str[i]-'a']==-1){
                    return 0;
                }
                p=ch[p][str[i]-'a'];
            }
            return cnt[p];
        }
        void erase(char *str){
            int p=0;
            for(int i=0;str[i];i++){
    			if(ch[p][str[i]-'a']==-1){
                    return;
                }
                p=ch[p][str[i]-'a'];
            }
            if(cnt[p]){//是单词不是前缀
                --cnt[p];
            }
        }
    };
    int main() {
        Trie name;
        name.init();
        name.insert("barty");
        name.insert("islands");
        cout<<name.find("islands")<<endl;
        cout<<name.find("bar")<<endl;
        name.erase("islands");
        cout<<name.find("islands")<<endl;
        return 0;
    }
    

    区别:
    KMP:在主串S中找子串T的位置KMP算法的时间复杂度O(|S|+|T|)。

    扩展KMP: 给定串S,和串T,设S的长度为n,T的长度为m,求T与S的每一个后缀(包括S)的最长公共前缀。复杂度为O(n+m)。

    字典树上的动态规划
    识别
    在这里插入图片描述
    这道题发现还要用到乘法原理,故这里求方案数也可以使用dp,类似还有求n能被多少个完全平方数分

    const int maxn=50000;
    const int maxc=26;
    struct Trie{
    	char T[maxn];
        int ch[maxn][maxc];
        int tot;
        int cnt[maxn],dp[maxn];
        void init(){
            tot=0;
            memset(cnt,0,sizeof(cnt));
            memset(ch,-1,sizeof(ch));
             memset(dp,0,sizeof(dp));
        }
        void insert(char *str){
            int p=0;
            for(int i=0;str[i];i++){
                if(ch[p][str[i]-'a']==-1){
                    ch[p][str[i]-'a']=++tot;
                }
                p=ch[p][str[i]-'a'];
            }
            cnt[p]++;
        }
        void find(int st){
            int p=0;
            for(int i=st;T[i];i++){//这里查找的目的是实现转移,故从st开始找
    			if(ch[p][T[i]-'a']==-1){
                    return;
                }
                p=ch[p][T[i]-'a'];
                if(cnt[p]){
                	dp[i]+=dp[st-1];
                }
            }
        }
    };
    
    int main() {
        Trie word;
        word.init();
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
    		char s[110];
            cin>>s;
            word.insert(s);
        }
        scanf("%s",word.T+1);//方便动规从1开始
        word.dp[0]=1;
        int i;
        for(i=1;word.T[i];i++){
    		word.find(i);
        }
        cout<<word.dp[i-1]<<endl;
        return 0;
    }
    

    例题
    KMP
    (1)周期
    求一个字符串的最小循环节:
    n%((n-1)-fail[n-1])==0;
    (2)字符串消消乐
    循环的s中找到t的第一个位置并删除,直到找不到。
    难点:
    消掉一个后,前面或许有能和后面出现满足答案的公共部分。
    为避免重复匹配(消掉一次再消一次),这里借助栈,栈中存储最大匹配状态,每删除一个后对应删除在栈中的最大匹配状态
    将位置存入栈,匹配完,退栈,再取出栈顶,再匹配

    拓展KMP
    (1)首位相接
    求两字符串的首位的最大重复部分:
    目标:求出串S2的后缀和串S1的公共前缀
    i+extend[i]=S2的绝对值-1
    意思是S2的尾部几个被S1替代(相同)后,因为extend数组记录从0开始,故S2这里-1

    展开全文
  • 字典树KMP优先队列

    2015-03-17 21:46:13
    TJRAC_ACM 字典树KMP优先队列学习课件
  • kmp&字典树 模板

    2020-07-27 22:17:06
    kmp: const int maxn=1e5+5; char s[maxn],p[maxn]; int nex[maxn]; int KmpSearch(char* s, char* p) { int i = 0; int j = 0; int sLen = strlen(s); int pLen = strlen(p); while (i < sLen &&...

    kmp:

    const int maxn=1e5+5;
    char s[maxn],p[maxn];
    int nex[maxn];
    int KmpSearch(char* s, char* p)
    {
    	int i = 0;
    	int j = 0;
    	int sLen = strlen(s);
    	int pLen = strlen(p);
    	while (i < sLen && j < pLen)
    	{
    		//①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++    
    		if (j == -1 || s[i] == p[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			//②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]    
    			//next[j]即为j所对应的next值      
    			j = nex[j];
    		}
    	}
    	if (j == pLen)
    		return i - j;
    	else
    		return -1;
    }
    void GetNext(char* p,int next[])
    {
    	int pLen = strlen(p);
    	nex[0] = -1;
    	int k = -1;
    	int j = 0;
    	while (j < pLen - 1)
    	{
    		//p[k]表示前缀,p[j]表示后缀
    		if (k == -1 || p[j] == p[k]) 
    		{
    			next[++j] = ++k;
    		}
    		else 
    		{
    			k = next[k];
    		}
    	}
    }
    //优化过后的next 数组求法
    void GetNextval(char* p, int next[])
    {
    	int pLen = strlen(p);
    	next[0] = -1;
    	int k = -1;
    	int j = 0;
    	while (j < pLen - 1)
    	{
    		//p[k]表示前缀,p[j]表示后缀  
    		if (k == -1 || p[j] == p[k])
    		{
    			++j;
    			++k;
    			//较之前next数组求法,改动在下面4行
    			if (p[j] != p[k])
    				next[j] = k;   //之前只有这一行
    			else
    				//因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
    				next[j] = next[k];
    		}
    		else
    		{
    			k = next[k];
    		}
    	}
    }

      字典树:

    const int maxn=1e5+5;
    int trie[maxn][26];
    int sum[maxn];
    int exist[maxn];
    char s[maxn];
    int tot=0;
    void insert(char s[])  //插入字符串;
    {
        int len=strlen(s);
        int root=0;
        for(int i=0;i<len;i++)
        {   
            int id=s[i]-'a';
            if(trie[root][id]==0)
            {
                trie[root][id]=++tot; //tot新建节点编号;
                exist[root]=0;
            }
            root=trie[root][id];
            sum[root]++;   //表示有相同该前缀的单词个数;
        }
        exist[root]=1;   //该节点是存入的单词最后一位可以用来查询是否有这个单词;
    }
    // 查找是否为插入单词
    bool find(char s[])
    {
        int len=strlen(s);
        int root=0;
        for(int i=0;i<len;i++)
        {
            int id=s[i]-'a';
            if(trie[root][id]==0)  //不存在直接退出;
            {
                return false;
            }
            root=trie[root][id];
        }
        if(exist[root])
        {
            return true;
        }
        else return false;
    }
    // 查找前缀为 s出现的次数;
    int find_sum(char s[])
    {
        int len=strlen(s);
        int root=0;
        for(int i=0;i<len;i++)
        {
            int id=s[i]-'a';
            if(trie[root][id]==0)
            {
                return  0;
            }
            root=trie[root][id];
        }
        return sum[root];
    }

     

    展开全文
  • KMP中的一个重要思想与AC自动机非常相似,就是失配指针。在kmp算法中指匹配失败后该返回到字符串的哪个位置,也就是俗称的特定位置的复活出生点。 KMP模板如下: //#include<pch.h> #include <iostream&...
  • 字典树vskmp

    2018-01-14 13:19:32
    字典树 字典树目的在于可以节省大量空间存储单词或其他字符串,并且可以快速查找。 poj3630 题意: 给出若干字符串,判断某个字符串是否是其他字符串的前缀,有这样的字符串输出“NO”,否则输出“YES”。 ...
  • KMP const int inf=0x3f3f3f; const int maxn=1e6+6; const int base=32; const int mod = 1e9+7; char a[maxn],b[maxn]; ll lena,lenb; int next1[maxn]; void getnext(){ next1[0]=-1; int i=0,j=-1; while(i&...
  • AC自动机(KMP+字典树) 题目:输入N个串,判断有多少个搜索串的子串 In out 1 4 7 a ab abc abcd abcde abcdef abcdefg abcd #include&lt;bits/stdc++.h&gt; using namespace std; char str[1000000+...
  • 字典树+KMP

    2019-05-10 21:17:35
    KMP算法专门解决长文本的单模板匹配问题,字典树专门解决单个单词(短文本)多模板匹配问题。而AC自动机解决的是长文本的多模板匹配问题。且AC自动机不但时间上具有优势,空间上也颇具优势。 AC自动机需要事先知道...
  • //数组做法 #include<bits/stdc++.h> using namespace std;... //字典树 int cntword[100000]; //记录该单词出现次数 int fail[100000]; //失败时的回溯指针 int cnt = 0; void Insert(char s[]) { int...
  • [leetcode 面试题 17.17] -- 多次搜索题目来源分析KMP思路完整代码字典树完整代码 题目来源 https://leetcode-cn.com/problems/multi-search-lcci/ 分析 题目就是让从一长串字符中,搜索最多1e5个字符串,找到所有...
  • 先贴几个板子,记录一下 kmp为单模匹配算法,这个博客讲的很好:https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html,透彻明了,...//kmp和优化后的kmp #include <iostream> #include <cstring&g...
  • 查询一个文本串中模式串出现的次数,需要构建字典树,而这里如何将两者联系到一起呢?就是将字典树上的next数组构造变成了给每个节点找fail指针。 关键点1:字典树构造 比方说我们有五个模板串:she shr say ...
  • 字符串匹配的三个算法(KMP+字典树+AC自动机)

    万次阅读 多人点赞 2017-12-18 17:13:50
    字符串匹配算法,KMP字典树,AC自动机。 分别对应一对一匹配,一对多匹配,多对多匹配。
  • 字典树 概念: 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符...
  • 学习AC自动机之前要先学会字典树kmp, 这里我都会简单提一下。  字典树字典树恰如其名, 真的是和字典非常的类似, 当我们在字典上查找单词的时候都是先找第一个字母确定大概范围,然后再找其它字母逐渐缩小...
  • 然后就是具体做法,正串放入字典树内,如果某个位置的的下一个位置pos是一个回文(这个根据上面的EX_KMP处理出来)val[pos]++; 插入完后就在最后一个节点的位置pos,ed[pos]++; 最后一步计算答案; 字典树...
  • 将该串加入到字典树中,假设当前节点为u,对于某个位置i,如果i往后正好是一个回文串,则val[u]++。 插入完该串后,尾节点u的spj[u]++。 所有字符串插入完后,开始查找并计算答案。 对于字符串s,我们将它...
  • 回文串的性质 : 它的每个前缀都...kmp求出所有串的前缀回文串和后缀回文串然后把正序串依次存入字典树,然后枚举反序串进行查询与字典树上的串进行匹配得出结果。 坑了两个晚上#include #include #include #define LL
  • 字典树中的参数huiwen记录从该字母开始回文串的个数,注意回文记录的只是以正串为后缀的个数 另外:因为只给了字符串的总长度,所以,只开一维的字符串数组,每次接着上次字符串结束的位置开始即可。为了方便,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,113
精华内容 2,045
热门标签
关键字:

kmp字典树