正文

codevs——t1404字符串匹配

Aptal丶  Aptal丶  2022-09-15  247

关键词：

http://codevs.cn/problem/1404/

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

给你两个串A，B，可以得到从A的任意位开始的子串和B匹配的长度。
给定K个询问，对于每个询问给定一个x，求出匹配长度恰为x的位置有多少个。
N，M，K<=200000

输入描述 Input Description

第一行三个数 N，M，K，表示A的长度、B的长度和询问数。
第二行为串A。
第三行为串B。
接下来K行，每行1个数X。

输出描述 Output Description

对于每个询问输出一个数。

样例输入 Sample Input

6 2 2
aabcde
ab
0
2

样例输出 Sample Output

4
1

数据范围及提示 Data Size & Hint

各个测试点1s

exkmp~~~ctrl_c+ctrl_v

假如有匹配串A长度为N，模式串B长度为M，那么扩展KMP算法可以在O(N+M)的时间内算出对于A的每一个位置，与B的最长匹配长度是多少（即与B串前缀重合的最长长度），算法如下：

PART_1 初始化next数组

设next[i]表示B串的i位置开始的字符串与B串的前缀的最长重合长度（注意这里与KMP中的next是不一样的）。明显地，next[1]=M（我的字符串的下标习惯从1开始），next[2]也可以用一个简单的for循环求出，pos初始化为2；当i∈[3,M]时，我首先认为关于1~i-1的信息已全部求出，我们记录一个pos，它的意义是当前已计算出的next数组中，j+next[j]-1能达到的最右端所对应的i，这个不太好理解，可以参考manacher算法的思想戳这（其实manacher和扩展kmp是很像的），令rp=pos+next[pos]-1

(1)当i+next[i-pos+1]<rp时，易得next[i]=next[i-pos+1]

(2)当i+next[i-pos+1]>=rp时，rp后的元素，即b[rp+j]，可能会和b[rp-i+1+j]相等，这时进行暴力扩展，如果扩展发生，则更新pos为i，next[i]直接在扩展中求出。

注意：有时rp可能小于i，这时可以加一特判，直接进行暴力求

PART_2 匹配

令ans[i]表示a串中以a[i]为开头的后缀和b串的最长匹配长度，设pos表示a串中对于所有的i，i+ans[i]-1能达到的最远位置对应的i，rp就是pos+ans[pos]-1，next[1]暴力求出，pos初始化为1；当i∈[2,N]时：

(1)若i+next[i-pos+1]-1<rp，则ans[i]=next[i-pos+1]

(2)若i+next[i-pos+1]-1>=rp，则进行暴力扩展，同时更新pos，ans在扩展时求出

注意：如果rp<i，那么加一特判，直接暴力扫描

这个题就明了了~~~

 1 #include <algorithm>
 2 #include <cstring>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 const int N(200000+5);
 8 int n,m,k,lb,la;
 9 int p[N],ans[N];
10 char a[N],b[N];
11 
12 inline void Get_next()
13 {
14     for(int i=2,j=0;i<=lb;p[i++]=j)
15     {
16         for(;b[i]!=b[j+1]&&j>0;) j=p[j];
17         if(b[i]==b[j+1]) j++;
18     }
19 }
20 inline void kmp()
21 {
22     for(int i=1,j=0;i<=la;i++)
23     {
24         for(;a[i]!=b[j+1]&&j>0;) j=p[j];
25         if(a[i]==b[j+1]) j++;
26         ans[j]++;
27     }
28 }
29 
30 int main()
31 {
32     scanf("%d%d%d%s%s",&n,&m,&k,a+1,b+1);
33     la=strlen(a+1); lb=strlen(b+1);
34     Get_next(); kmp();
35     for(int i=lb;i>0;i--) ans[p[i]]+=ans[i];
36     for(int i=0;i<lb;i++) ans[i]-=ans[i+1];
37     for(int pos;k--;)
38     {
39         scanf("%d",&pos);
40         printf("%d
",ans[pos]);
41     }
42     return 0;
43 }

codeves1222

思路：先得到最大匹配，不为n，none，对于每个边,假如不可获缺,那么没有它一定无法完美匹配,对匹配的边依次删除,如果不能完美匹配就输出1#include<bits/stdc++.h>2usingnamespacestd;3constintN=102;45inta[N][N],vis[N];6intc[N],d[N];7intn;8boolFind(... 查看详情

codevs1222信与信封的问题

二分图匹配。先匹配一次，一定是完美匹配。然后枚举每条边，去掉它，若是不能完美匹配，这条边就必须。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<queue>#include<vect 查看详情

codevs1922骑士共存问题（最小割，二分图最大匹配）

...互不攻击。n<=200,m<=n^2 思路：经典的二分图最大匹配问题，采用黑白点染色的思想。如果按照相邻点黑白不同染色，可以发现每次跳到的点必定与现在所在点不同色，查看详情

矩阵游戏|zjoi2007|bzoj1059|codevs1433|luogup1129|二分图匹配|匈牙利算法|elena

1059:[ZJOI2007]矩阵游戏TimeLimit: 10Sec MemoryLimit: 162MBDescription　　小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是... 查看详情

codevs1409拦截导弹2

...接排序后n²的dp即可。　　第二问我们考虑二分图匹配，连边后转换模型成为最小路径覆盖。代码：//codevs1409 查看详情

codevs1022覆盖

【算法】二分图匹配(最大流)【题解】对i+j进行奇偶染色，就可以保证相邻两格异色。然后就是二分图了，对相邻格子连边跑最大流即可。#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintmaxn=110,maxN=10100,in... 查看详情

codevs1084乒乓球

...须大于2,（按照实际的规则弄得，题目中没有说）2.读入字符串的时候，E标志着字符串的结尾，但是也要读进字符串。例如：WWWWWWWWWWWE（11个W，一个E）：程序的输出结果应该是：11:00:0而不应该只是：11:0 代码：#include<iostrea 查看详情

后缀数组-codevs1500

后缀数组的原理很简单，将一个字符串S的所有后缀组成一个字符串数组，并排序，则以后每次判断某个字符串D是不是S的子串只需要strlen(D)*log(strlen(s))的时间复杂度。Codevs1500这题就是一道裸题，考后缀数组的生成... 查看详情

codevs1013求先序排列

...大写字母表示，长度<=8）。输入描述InputDescription两个字符串，分别是中序和后序（每行一个）输出描述OutputDescription一个字符串，先序样例输入SampleInputBADCBDCA样例输出Sa 查看详情

codevs3031最富有的人[字典树]

...这是蒟蒻写的第一道字典树……听说出市选题的神犇要出字符串，于是就赶紧滚去学了学（然而高精度算字符串算法？）　　简单来说，字典树就是把一坨字符串按照字典序储存起来。然而，直接把字符串排序太浪费空间，而且... 查看详情

squarewords（codevs3301）

...nbsp;words，但是abcabcab和aaaaa都不是。现在有一个长度为n的字符串，求至少要删掉多少个字符，使得剩下的字符串是square words。输入描述 InputDescription第一行包含一个查看详情

后缀排序（codevs1500）

...。Prof. HandsomeG给了他一个长度为n的由小写字母构成的字符串，要求他把该字符串的n个后缀(suffix)从小到大排序。何谓后缀？假设字符串是S=S1S2……Sn，定义Ti=SiSi+1……Sn。T1, T2, …, Tn就叫做S的n个后缀。关于字符串... 查看详情

codevs1204寻找子串位置题解

...题目链接：http://codevs.cn/problem/1204/题目描述Description给出字符串a和字符串b，保证b是a的一个子串，请你输出b在a中第一次出现的位置。输入描述InputDescription仅一行包含两个字符串a和b输出描述OutputDescription仅一行一个整数样例输... 查看详情

codevs2884字符等式

2884字符等式题目描述 Description现在,我们有一个用卡片组成的等式(卡片仅仅是数字和=号)虽然是等式但是它却是错误的.....后来你觉得,似乎在这个等式左侧的某个地方添上一个加号“+”就可以使等式成立...但是,,等... 查看详情

codevs2875ry哥查字典

...n1个整数N,表示字典里面的单词数量。接下来N行,每行一个字符串,表示一个单词。然后第N+2行,一个整数M,表示要查的单词数。接下来M行,每行一个字符串,表查看详情

codevs1922骑士共存问题

【算法】二分图最大匹配(最大流)【题解】按(i+j)奇偶性染色后，发现棋子跳到的地方刚好异色。然后就是二分图了，对于每个奇点向可以跳到的地方连边，偶点不需连(可逆)。所以题目要求转换为求二分图上最大独立集(对于每... 查看详情

codevs3160最长公共子串

...bsp; 题目描述 Description给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。输入描述 InputDescription读入两个字符串输出描述& 查看详情

codevs1204寻找子串位置

题目描述 Description给出字符串a和字符串b，保证b是a的一个子串，请你输出b在a中第一次出现的位置。输入描述 InputDescription仅一行包含两个字符串a和b输出描述 OutputDescription仅一行一个整数样例输入 SampleInputabcdbc样... 查看详情