fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char text[1000010],pat[1000010];
  4. void compute_lps(char* pat,int m,int lps[]){
  5.     int len=0;
  6.     lps[0]=0;
  7.     int i=1;
  8.     while(i<m){
  9.         if(pat[i]==pat[len]){
  10.             len++;
  11.             lps[i]=len;
  12.             i++;
  13.         }
  14.         else{
  15.             if(len!=0) len=lps[len-1];
  16.             else{
  17.                 lps[i]=0;
  18.                 i++;
  19.             }
  20.         }
  21.     }
  22. }
  23.  
  24. void kmp(char* text,char* pat){
  25.     int n=strlen(text);
  26.     int m=strlen(pat); bool flag=true;
  27.     int lps[m];
  28.     compute_lps(pat,m,lps);
  29.     int i=0; //index for text
  30.     int j=0; //index for pat
  31.     while(i<n){
  32.         if(text[i]==pat[j]){
  33.             i++; j++;
  34.         }
  35.         if(j==m){
  36.             printf("%d\n",i-j);
  37.             j=lps[j-1];
  38.         }
  39.         else if (i<n && pat[j]!=text[i]){
  40.             if(j!=0) j=lps[j-1];
  41.             else
  42.                 i=i+1;
  43.         }
  44.     }
  45.     if(flag) printf("\n");
  46. }
  47. int main()
  48. {
  49.     int n;
  50.     while(scanf("%d %s %s",&n,pat,text)!=EOF){
  51.     kmp(text,pat);
  52.     }
  53.     return 0;
  54. }
  55.  
  56.  
Success #stdin #stdout 0s 17192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jV2n7D
language:
C++14 (gcc 8.3)
created:
7 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!