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 }