首页 > 其他分享 >AcWing 831.KMP字符串

AcWing 831.KMP字符串

时间:2022-11-21 01:33:21浏览次数:38  
标签:10 831 int next KMP 字符串 输入 AcWing

AcWing 831.KMP字符串

题目描述

给定一个字符串 S,以及一个模式串 P ,

所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P 在字符串 S 中多次作为子串出现。

求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N,表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M ,表示字符串 S 的长度。

第四行输入字符串 S。

输出格式

共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。

数据范围

1≤N≤10^5
1≤M≤10^6

输入样例

3
aba
5
ababa

输出样例

0 2

题目思路

KMP模板题,next数组与数据数组都从1开始存储。
next数组求值方法:
我们能确定next数组第一位一定为0(第0位也为0),后面求解每一位的next值时,根据前一位进行比较。
从第二位开始,将前一位与其next值对应的内容进行比较,
如果相等,则该位的next值就是前一位的next值加上1;
如果不等,向前继续寻找next值对应的内容来与前一位进行比较,
直到找到某个位上内容的next值对应的内容与前一位相等为止,
则这个位对应的值加上1即为需求的next值;
如果找到第一位都没有找到与前一位相等的内容,那么求解的位上的next值为1。

#include<cstdio>
#include<iostream>

using namespace std;

const int N = 1e5+10;
const int M = 1e6+10;

int n,m;
char p[N],s[M];
int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    
    for(int i=2,j=0;i<=n;i++)
    {
        while(j && p[i] != p[j+1]) j = ne[j];
        if(p[i] == p[j+1])j++;
        ne[i] = j;
    }
    
    for(int i=1,j=0;i<=m;i++)
    {
        while(j && s[i] != p[j+1]) j = ne[j];
        if(s[i] == p[j+1])j++;
        if(j == n)
        {
            cout << i - n << ' ';
            j = ne[j];
        }
    }
    
    return 0;
}

标签:10,831,int,next,KMP,字符串,输入,AcWing
From: https://www.cnblogs.com/fsh001/p/16910182.html

相关文章

  • 2022-11-20 Acwing每日一题
    本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我......
  • P8195 [传智杯 #4 决赛] 小智的疑惑 ----- 字符串匹配、KMP算法优化next数组
    题目描述传智专修学院给了小智一个仅包含小写字母的字符串 ss,他想知道,里面出现了多少次子串 chuanzhi 呢。我们称一个字符串 tt 是 ss 的子串,当且仅当将 ss 的......
  • KMP
    KMP算法模式串p:就是需要寻找的那个串文本串t:就是一个待与模式串p匹配的字符串作用:1.求出模式串p在文本串中出现的位置2.求出模式串长度为i的前缀的最长的border(就......
  • 2022-11-19 Acwing每日一题
    本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我......
  • AcWing 66. 两个链表的第一个公共结点 (2012算法题)
    题目:输入两个链表,找出它们的第一个公共结点。当不存在公共节点时,返回空节点。数据范围链表长度[1,2000]。保证两个链表不完全相同,即两链表的头结点不相同。样例 ......
  • 数据结构篇——KMP算法
    数据结构篇——KMP算法本次我们介绍数据结构中的KMP算法,我们会从下面几个角度来介绍:问题介绍暴力求解知识补充Next示例Next代码匹配示例匹配代码完整代码问题......
  • 2022-11-18 Acwing每日一题
    本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我......
  • [AcWing 792]高精度减法
    点击查看代码#include<iostream>#include<vector>usingnamespacestd;//判断A>=B返回trueA<B返回falseboolcmp(vector<int>A,vector<int>B){//当A的......
  • kmp算法(Java)
    详解参考:KMP算法讲解next数组求法方式1移动位数=已匹配的字符数-对应的部分匹配值已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹......
  • 2022-11-18 Acwing每日一题
    本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我......