fork download
copy 
  1. //
  2. //  main.cpp
  3. //  KMP Algorithm
  4. //
  5. //  Created by Himanshu on 31/05/23.
  6. //
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <string>
  11. using namespace std;
  12.  
  13. void printVector (vector<int> vec) {
  14.     for (int x : vec) {
  15.         cout<<x<<" ";
  16.     }
  17.     cout<<endl;
  18. }
  19.  
  20. vector<int> constructLPS (string pattern) {
  21.     int n = (int) pattern.length();
  22.     vector<int> lps(n, 0);
  23.     int j = 0;
  24.  
  25.     for (int i = 1; i < n; i++) {
  26.  
  27.         if (pattern[i] == pattern[j]) {
  28.             j++;
  29.         } else {
  30.             while (j > 0 && pattern[i] != pattern[j]) {
  31.                 j = lps[j-1];
  32.             }
  33.  
  34.         }
  35.  
  36.         lps[i] = j;
  37.     }
  38.  
  39.     return lps;
  40. }
  41.  
  42. void kmpStringSearch (string text, string pattern) {
  43.     int n = (int) text.length();
  44.     int m = (int) pattern.length();
  45.     vector<int> lps = constructLPS(pattern);
  46.  
  47.     int i = 0;
  48.     int j = 0;
  49.     int count = 0;
  50.  
  51.     while (i < n) {
  52.  
  53.         cout<<endl<<"Iteration "<<++count<<":"<<endl;
  54.         cout<<"i = "<<i<<", text[i] = "<<text[i]<<endl;
  55.         cout<<"j = "<<j<<", pattern[j] = "<<pattern[j]<<endl;
  56.  
  57.         if (text[i] == pattern[j]) {
  58.             i++;
  59.             j++;
  60.         }
  61.  
  62.         if (j == m) {
  63.             cout<<endl<<"Pattern found at index "<< i - j<<endl;
  64.             j = lps[j-1];
  65.         } else if (i < n && text[i] != pattern[j]) {
  66.  
  67.             if (j != 0) {
  68.                 j = lps[j-1];
  69.             } else {
  70.                 i++;
  71.             }
  72.         }
  73.  
  74.     }
  75.  
  76. }
  77.  
  78. int main() {
  79.     string text = "BABABA";
  80.     string pattern = "ABA";
  81.  
  82.     kmpStringSearch(text, pattern);
  83.  
  84.     return 0;
  85. }
Success #stdin #stdout 0.01s 5404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Iteration 1:
i = 0, text[i] = B
j = 0, pattern[j] = A

Iteration 2:
i = 1, text[i] = A
j = 0, pattern[j] = A

Iteration 3:
i = 2, text[i] = B
j = 1, pattern[j] = B

Iteration 4:
i = 3, text[i] = A
j = 2, pattern[j] = A

Pattern found at index 1

Iteration 5:
i = 4, text[i] = B
j = 1, pattern[j] = B

Iteration 6:
i = 5, text[i] = A
j = 2, pattern[j] = A

Pattern found at index 3
https://ideone.com/L8r2oW
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!