Algorithm: pattern searching

 1 #include <iostream>
 2 #include <map>
 3 #include <vector>
 4 #include <algorithm>
 5 #include <string>
 6 
 7 using namespace std;
 8 
 9 int main()
10 {
11     string pattern = "ABCABC";
12     string s = "ABCABCABCABCBCABC";
13     vector<int> lps(pattern.size());
14     int len = 0;
15     int i = 1;
16     lps[0] = 0;
17     while (i < pattern.size()) {
18         if (pattern[i] == pattern[len]) {
19             len++;
20             lps[i] = len;
21             i++;
22         }
23         else if (len != 0) len = lps[len-1];
24         else {
25             lps[i] = 0;
26             i++;
27         }
28     }
29     //for (int i = 0; i < pattern.size(); i++) cout << lps[i] << endl;
30     i = 0;
31     int j = 0;
32     while (i < s.size()) {
33         if (s[i] == pattern[j]) {
34             j++;
35             i++;
36         }
37         if (j == pattern.size()) {
38             cout << i - j << endl;
39             j = lps[j-1];
40         }
41         else if (pattern[j] != s[i]) {
42             if (j != 0) j = lps[j-1];
43             else i++;
44         }
45     }
46     return 0;
47 }