首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    序列自动机

    今天刚学了序列自动机感觉挺妙的; 这个就是给你一个母串,再给一下子串让你判断哪些子串是他的子串 这时候我们可以先对母串进行预处理一下: 用一个二维数来记录第i个位置后面的每个字母出现的第一个位置,dp[i][j]表示第 i 个位置以后字母 j 第一次出现的位置;当这个预处理结束后我们在查找的时候就可以找到这个字母的位置后再从这个位置查找下个字符这样一直跳着来查询就可以很快的查找结束了 预处理 我们可以从后向前慢慢的遍历这样一个循环就好了,但是注意存储的时候需要从第一个数开始,初始化的时候把数组初始化为 -1 ;比如 第 i+1 个字符是 a 那么dp[i][a]=i+1;其他的字符都是dp[i][b]=dp[i+1][b]; 查找 i=0; 直接从dp[i][x] (x为需要判断的子串的第一个字符);然后每次更新 i 的位置,顺序的遍历需要判断的子串的每个字符就可以了,一旦遇到 -1 就结束说明不可能是;

    04
    领券