今天我们学习了字符串算法内容有一些晦涩难懂需要我们仔细体会。但是老师讲的真的很好QAQ在我与同学进行思维的碰撞之后终于搞懂了。便马不停蹄地写博客以加深自己的印象。一.字符串哈希哈希就是将一个字符串以某种方式即哈希函数映射成一个数字便于O1来比较字符串是否相同通常哈希函数是将字符串的每个字符的ASCLL码处理成一个数后看成进制数。应当是一个大质数通过数学证明可以知道这样做可以减少哈希冲突即不等于,但是它们的函数值却相等会导致错误。但是得到的数将会太大可能需要高精度可那样和原来又有什么区别呢于是应模一个超大质数它应当是一个大质数通过数学证明可以知道这样做可以减少哈希冲突即不等于,但是它们的函数值却相等会导致错误。由于我对他理解较为透彻便不多赘述。二.KMP算法KMP算法全称Knuth-Morris-Pratt字符串查找算法由三位发明者的姓名命名是可以在文本串s中快速查找模式串p的一种算法。看课件较好理解便不多赘述。暴力int i0,j0; while(is.length()){ if(s[i]p[j]) i, j; else i i - j 1, j 0; if (j p.length()) // 匹配成功 { // 对s[i - j .. i - 1]进⾏⼀些操作 cout i - j endl; i i - j 1; j 0; } }跳跃for (int i 0, j 0; i s.length(); i) { while (j s[i] ! p[j]) j pmt[j - 1]; // 不断前移j指针直到成功匹配或移 if (s[i] p[j]) j; // 当前位匹配成功j指针右移 if (j p.length()) { // 对s[i - j 1 .. i]进⾏⼀些操作 j pmt[j - 1]; } }求pmt即前后缀长度// pmt[0] 0; for (int i 1, j 0; i plen; i) { while (j p[i] ! p[j]) j pmt[j - 1]; if (p[i] p[j]) j; pmt[i] j; }三.manacharManacher算法俗称马拉车是一种与回文串有关的算法。预处理将每个间隙插入无关字符$后不断枚举回文中心i并不断更新lr即已知r最大的回文串将i与r的关系分类讨论若是ir则继承其之对应i1的回文长度否则暴力扩展。将每个i的回文长度以数组记录即可。四.最小表示法字符串的最小表示为该字符串所有的循环同构字符串中最小字典序的一个。如abcde那么 的循环同构有abcdebcdeacdeabdeabceabcd其 中最小字典序的是 该串被称为 的最小表示。可以使用ij两个指针i初始指0j初始指1定义k表示当前以ij开头的两个长度为k的字符串当a[ik]a[jk]则k若有一方大则越过绊脚石跳到i/jk1且k清零。若ij重合则ij任意一个1即可代码如下int i0,j1,k0; while(injnkn){ int cmpa[(ik)%n]-a[(jk)%n]; if(cmp0){ k; } else{ if(cmp0){ iik1; } else{ jjk1; } if(ij){ j; } k0; } } int ansmin(i,j); for(int i0;in;i) couta[(ians)%n] ;