fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. vector<int> compute_pi(string pat) {
  6.   int n = pat.length();
  7.   vector<int> pi(n);
  8.   pi[0] = 0;
  9.   for (int i = 1; i < n; i++) {
  10.     pi[i] = 0;
  11.     int j = pi[i - 1]; /* trying length j + 1 */
  12.     while (j > 0 && pat[j] != pat[i]) {
  13.       j = pi[j - 1];
  14.     }
  15.     if (pat[j] == pat[i]) {
  16.       pi[i] = j + 1;
  17.     }
  18.   }
  19.   return pi;
  20. }
  21.  
  22. vector<int> find_matches(string text, string pat) {
  23.   int n = pat.length(), m = text.length();
  24.   string s = pat + "$" + text;
  25.   vector<int> pi = compute_pi(s), ans;
  26.   for (int i = n + 1; i <= n + m; i++) { /* n + 1 is where the text starts */
  27.     if (pi[i] == n) {
  28.       ans.push_back(i - 2 * n); /* i - (n - 1) - (n + 1) */
  29.     }
  30.   }
  31.  return ans;
  32. }
  33.  
  34. int main() {
  35. 	string abc = "abcddbcaaabcadacdba"; 
  36. 	vector<int> ans = compute_pi("abcddbcaaabcadacdba");
  37. 	for(int i = 0 ; i < ans.size() ; i++) {
  38. 	cout << abc[i] << " " << ans[i] << endl;
  39. } 
  40. 	return 0;
  41. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
a 0
b 0
c 0
d 0
d 0
b 0
c 0
a 1
a 1
a 1
b 2
c 3
a 1
d 0
a 1
c 0
d 0
b 0
a 1
https://ideone.com/soR09O
language:
C++ (gcc 8.3)
created:
17 days 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!