首页 > 编程语言 >KMP 算法和 TIRE 树

KMP 算法和 TIRE 树

时间:2024-02-21 21:01:03浏览次数:36  
标签:匹配 TIRE ++ s2 算法 KMP 字符串 节点

1. KMP 算法

KMP 算法,是判断一个字符串是否在一个字符串中出现过,能够快速匹配字符串在文本串中的有无,位置,次数,我们在匹配字符串中可以找到失配点,就可以不用从 \(1\) 重新查找,从某个特定点进行查找,大大减小了时间复杂度。

考虑一组样例:

字符串:abcdf
文本串:abcdabcdef

我们来将他匹配,首先前 \(4\) 个字母都会匹配上,发现到了第 \(5\) 个,就匹配不上了。那么我们就将字符串移动到失配的点。

字符串:   abcdf  
文本串:abcdeabcdef

因此我们可以不用一位一位的找,就可以根据相同的字母来进行匹配。

一共有两步:先是处理 KMP 数组,接着是字符串匹配。

在处理 KMP 数组中,我们可以自己匹配自己,对于每个 j 并且
j 是拥有可继承性的。

 fup(i, 2, l2) {
   while (j && s2[i] != s2[j + 1]) {
     j = kmp[j];
   }
   if (s2[j + 1] == s2[i]) {
     j++;
   }
   kmp[i] = j;
 }

在进行字符串匹配,j 可以看做表示当前已经匹配完的模式串的最后一位的位置,如果失配,那么就不断向回跳,直到可以继续匹配,如果匹配成功,那么对应的模式串位置 \(++\)。

fup(i, 1, l1) {
    while (j > 0 && s2[j + 1] != s1[i]) {
      j = kmp[j];
    }
    if (s2[j + 1] == s1[i]) {
      j++;
    }
    if (j == l2) {
      j = kmp[j];
    }
}

例题:模板

2.TIRE 树

TIRE 树,能够判断一个字符串的前缀,在多个字符串是否出现过,在查询时,通过判断每个字符的前缀,从而减少时间复杂度。在建树中,通过公共前缀来减少空间。

我们来举个例子:怎么存 abc,abb,bca,bc

通过这样存,就能够将这些所有的字符串存起来。

在用字典树中,也需要两步,先将字符串插入,在进行查询。

在进行插入时,通过一个二维数组,id 表示每个节点的编号,每个 \(tire[i][x]\) 表示一条边,\(1-n\) 表示每个节点的编号,如果 \(tire[i][x]==0\) 表示 i 这个点没有边,而 \(cnt[i]!=0\) 表示这个点不是叶节点,它还能继续往下拓展字符,p 代表节点编号,通过 \(tire[p][x]\) 判断当前节点是否存在,在插入时,如果 p 节点没有边,那么就 \(++id\) 将这个边存上,最后将 p 更新成新节点的编号。

void insert(string s) {
  int p = 0;
  fup(i, 0, s.size() - 1) {
    int x = s[i]-'a';
    if (trie[p][x] == 0) trie[p][x] = ++id;
    p = trie[p][x];
    cnt[p]++;
  }
}

接着进行查询,其他都差不多,就在 \(tire[p][x]==0\) 时表示这个点就确实没有出现过了,因此我们返回 \(0\) 查找失败,最后如果要求每个字符串前缀出现的次数,那么就返回 \(cnt[p]\),表示每个字符串前缀的次数。

int find(string s) {
  int p = 0;
  fup(i, 0, s.size() - 1) {
    int x = fun(s[i]);
    if (trie[p][x] == 0) return 0;
    p = trie[p][x];
  }
  return cnt[p];
}

例题:模板

标签:匹配,TIRE,++,s2,算法,KMP,字符串,节点
From: https://www.cnblogs.com/gongyuchen/p/18026197

相关文章

  • 2024牛客寒假算法基础集训营5
    A.总数-1的个数#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){intn;cin>>n;intans=0;for(inti=1,x;i<=n;i++){cin>>x;if(x==1)c......
  • 2024牛客寒假算法基础集训营5
    2024牛客寒假算法基础集训营5比赛链接赛时出了五题,被自己不严谨的思维害惨了,之后的题晚几天再补,要开学了A.mutsumi的质数合数思路既不是质数也不是合数恐怕非1莫属了吧Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineall(x)x.begin()......
  • KMP
    记录18:162024-2-5目录1.KMP1.KMP先把我之前学时候的笔记拉过来数据结构学习第二十三天串的模式匹配(KMP算法)给定一段文本,从中找出某个指定的关键字目标给定一段文本:$string=s_0s_1.....s_{n-1}$给定一个模式:$pattern=p_0p_1......p_{m-1}$求\(pa......
  • day38 动态规划part1 代码随想录算法训练营 70. 爬楼梯
    题目:70.爬楼梯我的感悟:居然自己先写出来了!!继续努力!!理解难点:听课笔记:我的代码:classSolution:defclimbStairs(self,n:int)->int:ifn==1:return1dp=[0]*(n+1)dp[1]=1dp[2]=2foriinran......
  • 1 c++算法题解析-两个数之和
    //给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。//你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。//你可以按任意顺序返回答案。//示例1:////输入:nums=[2,7,......
  • 代码随想录算法训练营第二十四天 | 77. 组合
    组合已解答中等相关标签相关企业给定两个整数n和k,返回范围[1,n]中所有可能的k个数的组合。你可以按任何顺序返回答案。示例1:输入:n=4,k=2输出:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]示例2:输入:n=1,k=1输出:[[1]]提示:1<=n<=201<......
  • 图解一致性哈希算法
    一、背景在具体介绍一致性哈希算法之前,先问一个问题:为什么需要一致性哈希算法?下面我们通过一个案例来回答这个问题。假设有这么一种场景:我们有三台缓存服务器分别为:node0、node1、node2,有3000万个缓存数据需要存储在这三台服务器组成的集群中,希望可以将这些数据均匀的缓存到三台......
  • 算法-哈希表
    1.有效字母的异位词(LeetCode242)题目:给定两个字符串s和t,编写一个函数来判断t是否是s的字母异位词。若s和t中每个字符出现的次数都相同,则称s和t互为字母异位词。s和t仅包含小写字母思路:使用大小为26的数组存储单词中每个字母出现的次数因为题目限制了字......
  • 代码随想录算法训练营第二十四天|● 理论基础 ● 77. 组合
    回溯理论基础 回溯法,与递归有类似形式,本质是穷举(可能存在剪枝),效率并不高。回溯的模板:voidbacktracking(参数){if(终止条件){存放结果;return;}for(选择:本层集合中元素(树中节点孩子的数量就是集合的大小)){处理节点;......
  • 2024牛客寒假算法基础集训营4
    2024牛客寒假算法基础集训营4比赛地址A.柠檬可乐思路:简单的模拟,按照题目描述判断大小即可Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineall(x)x.begin()+1,x.end()voidsolve(){ inta,b,k; cin>>a>>b>>k; if(a>=k*b)cout<<&qu......