codevs1204寻找子串位置题解

关键词：

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。

题目链接：http://codevs.cn/problem/1204/

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio> 
 6 
 7 char a[1005],s[1005];
 8 int nxt[1005],len1,len2;
 9 
10 void calc_nxt()
11 {
12     int k = -1,j = 0;
13     nxt[0] = -1;
14     while(j < len2)
15     {
16         if(k == -1 || s[j] == s[k])
17         {
18             ++ k,++ j;
19             if(s[k] != s[j])
20                 nxt[j] = k;
21             else
22                 nxt[j] = nxt[k];
23         }
24         else
25             k = nxt[k];
26     }
27 }
28 
29 inline int KMP(int k)
30 {
31     int j = 0;
32     while(j < len1 && j < len2)
33     {
34         if(j == -1 || a[k] == s[j])
35             ++ k,++ j;
36         else
37             j = nxt[j];
38     }
39     if(j == len2) return k-j;
40     return -1;
41 }
42 
43 int main()
44 {
45     scanf("%s",a);
46     scanf("%s",s);
47     len1 = strlen(a),len2 = strlen(s);
48     calc_nxt();
49     printf("%d\n",KMP(0)+1);
50     return 0;
51 }

codevs1204寻找子串位置

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

1204寻找子串位置

1204寻找子串位置  时间限制:1s 空间限制:128000KB 题目等级:青铜Bronze题目描述 Description给出字符串a和字符串b，保证b是a的一个子串，请你输出b在a中第一次出现的位置。输入描述 InputDescription仅一行包含两个... 查看详情

codevs3160最长公共子串

 3160最长公共子串  时间限制:2s 空间限制:128000KB 题目等级:大师Master题解 查看运行结果  题目描述 Description给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。 输入描述 In... 查看详情

poj1204：wordpuzzles——题解

...大意：给一个字母表，求一些字符串的开端第一次出现的位置和字符串的方向（字符串可以按照八个方向放在字母表中可匹配的位置）———————————————&mda 查看详情

codevs3160最长公共子串（sam）(代码片段)

题解：因为父亲节点是第一个right集合不同的后缀所以我们用ac自动机匹配的方法向下找，不符合了就往父亲方向跳时间复杂度O（n）代码：#include<bits/stdc++.h>#definelllonglong#definerintregisterint#definerep(i,h,t)for(rinti=h;i<=t;i++)#defined... 查看详情

codevs——t1404字符串匹配

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

codevs1214线段覆盖题解

...创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：http://codevs.cn/problem/1214/题目描述Description   给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些... 查看详情

codevs1506传话题解

...创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：http://codevs.cn/problem/1506/题目描述Description一个朋友网络，如果a认识b，那么如果a第一次收到某个消息，那么会把这个消息传给b，以及所有a认识的人。如... 查看详情

codevs1048石子归并题解

...创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：http://codevs.cn/problem/1048/题目描述Description有n堆石子排成一列，每堆石子有一个重量w[i],每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的... 查看详情

codevs1080线段树练习题解

...创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：http://codevs.cn/problem/1080/题目描述Description一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子... 查看详情

codevs2989寻找somebody

2989寻找somebody题目描述 Description在一个n*m的方阵中寻找somebody的位置有可能k不存在输出“biantai”输入描述 InputDescription共n+1行第一行nmk后n行为方阵 输出描述 OutputDescription输出k的行和列样例输入 SampleInput... 查看详情

codevs1081线段树练习2题解

...创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：http://codevs.cn/problem/1081/题目描述Description给你N个数，有两种操作1：给区间[a,b]的所有数都增加X2：询问第i个数是什么？ 输入描述InputDescription第一行一个... 查看详情

codevs2989寻找somebody

...等级:钻石Diamond题目描述 Description在一个n*m的方阵中寻找somebody的位置有可能k不存在输出“biantai”输入描述 InputDescription共n+1行第一行nmk后n行为方阵 输出描述 OutputDescription输出k的行和 查看详情

算法题解之滑动窗口

SubstringwithConcatenationofAllWords寻找所有词连接的子串思路：由于该字串是所有词典中的词连接的，所以该字串长度固定。因此本题可以看作一个滑动窗口的题。为了去除重复工作，每次滑动一个单词的长度，因此起始位置就有n种... 查看详情

codevs4560noip2015d2t2子串

...字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串，然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串，请问有多少种方案可以使得这个新串与字符串B相等？注意：子串取出的位置不同... 查看详情

[codevs1204]单词背诵

题目描述灵梦有n个单词想要背，但她想通过一篇文章中的一段来记住这些单词。文章由m个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，... 查看详情

uva1204fungame

...题解】不难发现如果一个串的原串或反转串是另一个串的子串，那么这个串是没有用的我们把他剔除出去如果此时只有一个串，暴力枚举解检查即可（网上很多写法是KMP。。不是很明白，没仔细看他们代码多个串则状压DPdp[s][i 查看详情

[noip2015]子串substring题解

...字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串,然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串B相等?注意:子串取出的位置不同也认为... 查看详情