序列自动机

今天刚学了序列自动机感觉挺妙的; 这个就是给你一个母串,再给一下子串让你判断哪些子串是他的子串 这时候我们可以先对母串进行预处理一下: 用一个二维数来记录第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 就结束说明不可能是;

下面看个例题吧 子串查询:题目链接 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld 题目描述 给出一个长度为n的字符串s和q个查询。对于每一个查询,会输入一个字符串t,你需要判断这个字符串t是不是s的子串。子串的定义就是存在任意下标a<b<c<d<e,那么”s[a]s[b]s[c]s[d]s[e]”就构成s的一个子串。如”abc”的子串有”a”、”b”、”c”、”ab”、”ac”、”bc”、”abc”。 输入描述: 第一行两个数n,q。1<=n,q<=1e5。

第二行一个长度为n的字符串s,所有字符都为小写拉丁字符。

接下来q行每行一个字符串t。1<=|t|<=50。 输出描述: 对于每个查询,如果t是s的字串,输出”YES”,否则输出”NO”。每个答案占一行。 输入

8 4
ababcbaa
abac
accb
aaaa
abcba

输出

YES
NO
YES
YES
#include<bits/stdc++.h> 
using namespace std;
const int maxn=1e5+10;
char a[maxn],b[maxn];
int n,m;
int dp[maxn][30]; 
//构建动态的数组 
void build()
{
    memset(dp,-1,sizeof dp);//初始化的值只要不可能出现就行 
    //记录这个位置以后最先出现的字符 
    for(int j=n-1;j>=0;j--)//从倒数二个位置开始遍历 
    {
        for(int i=0;i<26;i++)// 判断这个位置的下个字符 i 的位置 
        {
            if(a[j+1]-'a'==i)// 如果下个字符是 i 就更新位置 
               dp[j][i]=j+1;
            else dp[j][i]=dp[j+1][i];// 如果不等就 和上个位置一样 
        }
    }
}

int main()
{
    //因为进行预处理的时候是这个位置以后最先出现的字符
    //所以不能从0开始存字符 ,要从1开始 
    scanf("%d%d%s",&n,&m,a+1);
    build();
    while(m--)
    {
        scanf("%s",b);
        int le=strlen(b);
        bool flag=0;
        int j=0;//初始化 j=0; 
        for(int i=0;i<le;i++)//顺序遍历子串的每个字符 
        {
            // 如果等于-1就结束 
            if(dp[j][b[i]-'a']==-1){
                flag=1;
                break;
            }
            j=dp[j][b[i]-'a'];//更新j的位置 
        }
        puts(flag?"NO":"YES");
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • F2. Animal Observation (hard version)

    time limit per test:3 seconds memory limit per test:512 megabytes inputstandard ...

    某些人
  • E. Permutation Separation

    E. Permutation Separation time limit per test:2 seconds memory limit per test:25...

    某些人
  • Dr. Evil Underscores

    time limit per test:1 second memory limit per test:256 megabytes inputstandard ...

    某些人
  • LeetCode 1289. 下降路径最小和 II(DP)

    给你一个整数方阵 arr ,定义「非零偏移下降路径」为:从 arr 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。

    Michael阿明
  • 漫画:美团面试题(整数拆分)

    这两天越来越多的读者私信小浩,说觉得只看题的话,不是很系统,想让我系统的讲一讲各类数据结构。对于这个问题,我统一回复一下,首先后面肯定是有系统的讲解各类数据结构...

    程序员小浩
  • 【POJ 1273】Drainage Ditches(网络流)

    一直不明白为什么我的耗时几百毫秒,明明差不多的程序啊,我改来改去还是几百毫秒。 ...一个小时后:明白了,原来把最大值0x3f(77)取0x3f3f3f3f就把...

    饶文津
  • JAVA基础复习day-01

    byte、int、long、和short都可以用十进制、16进制以及8进制的方式来表示。

    阮键
  • apache多站点配置汇总

    今天一个网友咨询多站点配置,于是就捣鼓了一番,现在总结出来给大家分享 多站点总的来说就三种:基于多ip多站点,基于单ip多域名多站点,基于单ip多端口站点 1、...

    苦咖啡
  • leetcode 一些算法题及答案

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    WindWant
  • 三种主流深度相机介绍

    深度相机又称之为3D相机,顾名思义,就是通过该相机能检测出拍摄空间的景深距离,这也是与普通摄像头最大的区别。

    点云PCL博主

扫码关注云+社区

领取腾讯云代金券