fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int lps[500000];
  4. char str[500000],str1[500000];
  5. int main(){
  6.     int x,i,j;
  7.     while(scanf("%d",&x)!=EOF){
  8.         scanf("%s",str);
  9.         scanf("%s",str1);
  10.         lps[0]=0;
  11.         i=1;
  12.         j=0;
  13.         while(i<strlen(str)){
  14.             if(str[i]==str[j]){
  15.                 lps[i]=j+1;
  16.                 i++;
  17.                 j++;
  18.             }
  19.             else if(j==0){
  20.                 lps[i]=0;
  21.                 i++;
  22.             }
  23.             else
  24.                 j=lps[j-1];
  25.         }
  26.         i=j=0;
  27.         while(i<strlen(str1)){
  28.             if(str1[i]==str[j]){
  29.                 i++;
  30.                 j++;
  31.             }
  32.             else if(j!=0)
  33.                 j=lps[j-1];
  34.             else
  35.                 i++;
  36.             if(j==strlen(str)){
  37.                 printf("%d\n",(i-j));
  38.                 j=lps[j-1];
  39.             }
  40.         }
  41.         printf("\n");
  42.     }
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0s 6340KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/A2N6An
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!