fork(2) download
copy 
  1. /*
  2.   Copyright 2012 Marek "p2004a" Rusinowski
  3.   Knuth-Morris-Pratt algorithm
  4. */ 
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8.  
  9. #define MAXN 1000000
  10.  
  11. int tab[MAXN], n, m;
  12. char str[MAXN], pat[MAXN];
  13.  
  14. void kmp(const char *str, const char *pat, int str_len, int pat_len, bool (*callback)(int idx, void *data), void *data = NULL) {
  15.   int a, i, *tab = (int *) malloc(str_len * sizeof(int));
  16.   tab[0] = 0;
  17.   for (i = 1; i < pat_len; ++i) {
  18.     tab[i] = tab[i - 1];
  19.     while (tab[i] > 0 && pat[tab[i]] != pat[i]) {
  20.       tab[i] = tab[tab[i] - 1];
  21.     }
  22.     if (pat[tab[i]] == pat[i]) {
  23.       ++tab[i];
  24.     }
  25.   }
  26.   for (a = 0, i = 0; i < str_len; ++i) {
  27.     while (a > 0 && pat[a] != str[i]) {
  28.       a = tab[a - 1];
  29.     }
  30.     if (pat[a] == str[i]) {
  31.       ++a;
  32.     }
  33.     if (a == pat_len) {
  34.       a = tab[a - 1];
  35.       if (!callback(i - pat_len + 1, data)) {
  36.         break;
  37.       }
  38.     }
  39.   }
  40.   free(tab);
  41. }
  42.  
  43. bool func(int a, void *) {
  44.   printf("%d\n", a);
  45.   return true;
  46. }
  47.  
  48. int main() {
  49.   scanf("%d%d%s%s", &n, &m, str, pat);
  50.   kmp(str, pat, n, m, func);
  51.   return 0;
  52. }
  53.  
Success #stdin #stdout 0.02s 8720KB
comments (?)
stdin
copy 
20 4
asdbmamarmamamaasqqq  
mama
stdout
copy 
4
9
11
https://ideone.com/ZaJYI
language:
C++ (gcc 8.3)
created:
12 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!