赞
踩
题目描述:
给定一个父字符串 s 和子字符串 p ,请按照从前向后的顺序,请求出 p 在 s 中所有出现的起始位置。
例如:s=ABADABCEABABA,p=ABA,则求解的结果是:1 9 11 。
输入:
第 1 行读入一个仅包含大写字母的字符串 s;
第 2 行读入一个仅包含大写字母的字符串 p ;
s 和 p 均是长度不超过 106 的字符串。
输出:
输出 1 行,按题意输出 p 在 s 中出现的位置,数字之间用空格隔开。
样例:
输入:
ABADABCEABABA ABA
输出:
1 9 11
- #include<bits/stdc++.h>
- using namespace std;
-
- const int N = 1e6 + 10;
- char s[N],p[N];
- //ne:存储p字符串前i个字符的最大前缀和后缀相同的长度
- int ne[N];
- int main(){
- scanf("%s%s",s+1,p+1);
- //计算ne数组
- ne[0] = ne[1] = 0;
- int lens = strlen(s+1),lent = strlen(p+1);
- for(int i = 1,j = 0;i < lent;i++){
- while(j && p[i+1]!=p[j+1]) j = ne[j];
- if(p[i+1] == p[j+1]) j++;
- ne[i+1] = j;
- }
-
- //尝试匹配父子字符串
- for(int i = 0,j = 0;i < lens;i++){
- while(j && s[i+1] != p[j+1]) j = ne[j];
- if(s[i+1] == p[j+1]) j++;
- //配对成功,输出起始位置
- if(j == lent){
- printf("%d ",i + 1 - lent + 1);
- j = ne[j];
- }
- }
- return 0;
- }
题目描述:
给定若干个长度≤106 的字符串,询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如:ababab 则最多有 3 个 ab 连接而成。
输入:
输入若干行(所有行的字符串的长度之和≤107),每行有一个字符串,字符串仅含英语小写字母。特别的,字符串可能为 .
即一个半角句号,此时输入结束。
输出:
对于每行输入,输出一个整数,代表计算的结果。
样例:
输入:
abcd aaaa ababab .
输出:
1 4 3
- #include<bits/stdc++.h>
- using namespace std;
- const int N=1e6+10;
- char s[N];
- int ne[N];
- int main(){
- while(scanf("%s",s+1)&&s[1]!='.'){
- ne[0]=ne[1]=0;
- int len=strlen(s+1);
- for(int i=1,j=0;i<len;i++){
- while(j&&s[i+1]!=s[j+1]) j=ne[j];
- if(s[i+1]==s[j+1]) j++;
- ne[i+1]=j;
- }
- if(len%(len-ne[len])==0) printf("%d\n",len/(len-ne[len]));
- else printf("%d\n",1);
- }
- return 0;
- }
题目描述
给定若干由小写字母组成的字符串(这些字符串总长 ≤4×105 ),在每个字符串中求出所有既是前缀又是后缀的子串长度。
例如:ababcababababcabab,既是前缀又是后缀的:
ab,abab,ababcabab,ababcababababcabab 。
输入:
输入若干行,每行一个字符串。
输出:
对于每个字符串,输出一行,包含若干个递增的整数,表示所有既是前缀又是后缀的子串长度。
样例:
输入:
ababcababababcabab aaaaa
输出:
2 4 9 18 1 2 3 4 5
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 4e5 + 10;
- char s[N];
- int ne[N];
- stack<int> st;
-
- int main(){
- while(scanf("%s",s+1) != EOF){
- //计算s字符串的next数组
- ne[0] = ne[1] = 0;
- int len = strlen(s+1);
- for(int i = 1,j = 0;i < len;i++){
- while(j && s[i+1] != s[j+1]) j = ne[j];
- if(s[i+1] == s[j+1]) j++;
- ne[i+1] = j;
- }
-
- //计算字符串s前缀和后缀相等的情况
- st.push(len);
- while(ne[len] != 0){
- st.push(ne[len]);
- len = ne[len];
- }
-
- //输出
- while(!st.empty()){
- printf("%d ",st.top());
- st.pop();
- }
- printf("\n");
- }
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。