题目:https://www.acwing.com/problem/content/833/
题意:求子串在母串中每次出现时的下标位置。
题解:哈哈哈,敲题时想到之前看到一个人叫 kmp 算法为 看毛片 算法,真是笑死我了hiahiahiahiahia。^ 。
该题的出现位置有点像暴力,跟循环节相关的题略有不同,在使用kmp的时候当与子串成功匹配时 j 的变化要注意,还有怎样输出下标。
代码:
1 #include <map> 2 #include <stack> 3 #include <queue> 4 #include <cmath> 5 #include <string> 6 #include <limits> 7 #include <cstdio> 8 #include <vector> 9 #include <cstdlib> 10 #include <cstring> 11 #include <iostream> 12 #include <algorithm> 13 #define Scc(c) scanf("%c",&c) 14 #define Scs(s) scanf("%s",s) 15 #define Sci(x) scanf("%d",&x) 16 #define Sci2(x, y) scanf("%d%d",&x,&y) 17 #define Sci3(x, y, z) scanf("%d%d%d",&x,&y,&z) 18 #define Scl(x) scanf("%I64d",&x) 19 #define Scl2(x, y) scanf("%I64d%I64d",&x,&y) 20 #define Scl3(x, y, z) scanf("%I64d%I64d%I64d",&x,&y,&z) 21 #define Pri(x) printf("%d\n",x) 22 #define Prl(x) printf("%I64d\n",x) 23 #define Prc(c) printf("%c\n",c) 24 #define Prs(s) printf("%s\n",s) 25 #define For(i,x,y) for(int i=x;i<y;i++) 26 #define For_(i,x,y) for(int i=x;i<=y;i++) 27 #define FFor(i,x,y) for(int i=x;i>y;i--) 28 #define FFor_(i,x,y) for(int i=x;i>=y;i--) 29 #define Mem(f, x) memset(f,x,sizeof(f)) 30 #define LL long long 31 #define ULL unsigned long long 32 #define MAXSIZE 100005 33 #define INF 0x3f3f3f3f 34 35 const int mod=1e9+7; 36 const double PI = acos(-1.0); 37 38 //using namespace std; 39 int next[MAXSIZE]; 40 void getnext(char *p) 41 { 42 int len=strlen( p); 43 int i=0; 44 int j=-1; 45 next[0]=-1; 46 while(i<len) 47 { 48 if(j==-1||p[i]==p[j]) 49 { 50 i++,j++; 51 next[i]=j; 52 } 53 else 54 j=next[j]; 55 } 56 } 57 void kmp(char *s,char *p) 58 { 59 getnext(p); 60 int i=0,j=0; 61 int lens=strlen(s); 62 int flag=0; 63 int lenp=strlen(p); 64 while(i<lens&&j<lenp) 65 { 66 if(j==-1||s[i]==p[j]) 67 { 68 i++; 69 j++; 70 } 71 else 72 j=next[j]; 73 if(j==lenp) 74 { 75 j=next[j];//注意这里,当匹配成功后,应该从母串对应片段的第二个字符开始,而不是直接跳过整个片段。 76 if(flag) 77 printf(" %d",i-lenp); 78 else 79 printf("%d",i-lenp); 80 flag=1; 81 } 82 } 83 } 84 int main() 85 { 86 int n,m; 87 char s[MAXSIZE],p[MAXSIZE]; 88 Sci(n); 89 Scs(p); 90 Sci(m); 91 Scs(s); 92 kmp(s,p); 93 return 0; 94 }
看毛片算法 哈哈哈。