字符串总结
这个寒假在家学完了字符串的3个基础知识点
1.字符串hash：很基础但又是很重要的算法
字符串hash在我浅薄的理解中分为1.unsigned写法//这应该是最常用的写法 2.mod写法//容易卡3.双hash写法，虽然很靠谱，但是卡的几率也比较大。
第二种分类可以用以上三种形式简单解决1.相等问题//两个字符串或子串的相等问题//这时候需要借助set集合，来去重。
2.匹配问题 ，就相当于一个区间内的匹配问题，这个可以归结到KMP算法中可能效率会高一点。
贴一段hash的标签吧
#include<bits/stdc++.h> using namespace std; unsigned long long value; unsigned long long base=131; int hash(string s) { value=0; for(int i=0;i<n;i++) value=value*base+s[i]-‘a‘+1;//不能从0开始 return value; } //双hash int mod1=1e+7; int mod2=1e+9; int hash1(string s) { value=0; for(int i=0;i<n;i++) value=(value*base+s[i]-‘a‘+1)%mod1; return value; } int hash2(string s) { value=0; for(int i=0;i<n;i++) { value=(value*base+s[i]-‘a‘+1)%mod2; } } //区间hash void setp() { p[0]=1; for(int i=1;i<n;i++) p[i]=p[i-1]*base; } void hash() { for(int i=0;i<n;i++) { has[i+1]=has[i-1]*p[i-1]+s[i]-‘a‘+1; } } void print() { cout<<has[r]-has[l-1]*p[r-l+1]<<endl; }
2.kmp算法
我们在hash中提到了--解决字符串匹配问题时我们就要用到kmp算法
在我这一段时间的刷题过程中，我所见到的kmp算法的几类有：1.简单的字符串问题2.解决字符串首尾一样的问题，这时候就是大概率用到字符串next数组的应用。3.统计字符在其中出现的个数的问题，这个问题就是要对kmp函数做一些处理，一般都是有规律可循的。等我有时间会将这些题放在上面的//gugugugu
#include<bits/stdc++.h> using namespace std; void getnext() { int j=-1; int i=0; next[i]==-1; for(int i=0;i<s.size();i++) { if(s[i]==s[j]||j==-1) { next[++i]=++j; } else j=next[j]; } } void kmp() { while(i<j.length()&&t<c.length()) { if(s[i]==s[j]||j==-1) { i++; j++; } else j=next[j]; } }
3.trie 字典树算法
字典树在我做的题中有一点局限//本人太菜了，没能解决一些难题，但是trie树对于单词的查找来说有一定的难以理解//虽然定义好理解但是代码还是有一点点难以理解的
字典树可以解决的问题有1.前缀问题//比较经典的一个题就是电话号码的问题。2.单词查找问题//绝了，我想到我还有一题没补，绝了绝了!
trie树有两种实现方式，一种是结构体，一种是二维数组问题，但是结构体不太好写，所以我习惯写数组//完蛋了，我觉得我要凉对于字典树
#include<bits/stdc++.h> using namespace std; int table[maxn][maxn]; void insert() { for(int i=0;i<s.size();i++) { t=s[i]-‘a‘; if(!visited[root][t]) { visited[root][t]=++tot; } root=visited[root][t]; } } void search() { for(int i=0;i<n;i++) { t=s[i]-‘a‘; if(!visited[root][t]) return 0; root=visited[root][t]; } }
关于字典树我会继续学习的！！
明天预告：1.ac自动机 2.马拉车 3.后缀数组//尽量明天完成
原文：https://www.cnblogs.com/liang0728/p/12332598.html