Skip to content

Instantly share code, notes, and snippets.

@dipta10

dipta10/KMP MultipleTimes #string.cpp

Created November 9, 2018 08:42
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dipta10/4658935c9f119fb7db966ba467c8dd7f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dipta10/4658935c9f119fb7db966ba467c8dd7f to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. dipta10 created this gist Nov 9, 2018.
    54 changes: 54 additions & 0 deletions KMP MultipleTimes #string.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,54 @@
    /*
    * Created by Dipta Das on 09-11-18
    */

    #include <bits/stdc++.h>
    #include <stdio.h>
    #define fin freopen("input", "r", stdin)

    using namespace std;

    vector<int> constructTempArray(string pattern) {
    vector<int> lps(pattern.length());
    int index = 0;
    for (int i = 1; i < (int) pattern.length(); ) {
    if (pattern[i] == pattern[index]) lps[i] = index + 1, ++index, ++i;
    else {
    if (index != 0) index = lps[index - 1];
    else lps[i] = index, ++i;
    }
    }
    return lps;
    }

    void KMPMultipleTimes (string text, string pattern) {
    bool found = false;
    vector<int> lps = constructTempArray(pattern);
    int j = 0, i = 0;

    // i --> text, j --> pattern
    while (i < (int) text.length()) {
    if (text[i] == pattern[j]) ++i, ++j;
    else {
    if (j != 0) j = lps[j - 1];
    else ++i;
    }

    if (j == (int) pattern.length()) {
    cout << "found match at : " << (i - pattern.length()) << endl;
    j = lps[j-1];
    found = true;
    }
    }

    if (!found) cout << "not found" << endl;
    }

    int main() {
    string text, pattern;
    getline(cin, text);
    getline(cin, pattern);
    KMPMultipleTimes(text, pattern);

    return 0;
    }