Created
October 16, 2018 23:12
-
-
Save iskakaushik/d9559db42e1e8b7c4919fb07c02867a8 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <string> | |
#include <vector> | |
#include <iostream> | |
using namespace std; | |
int main() { | |
string s; | |
cin >> s; | |
int n = s.length(); | |
int z[n]; | |
z[0] = 0; | |
// L and R are bounding box inclusives | |
int L = 0, R = 0; | |
// start conputing the prefix match from idx | |
auto z_start = [&](int idx) { | |
L = R = idx; | |
int j = 0; | |
while((L + j < n) && (s[j] == s[L + j])) j++; | |
R = L + j - 1; | |
z[idx] = j; | |
}; | |
for (int i = 1; i < n; i++) { | |
if (i > R) { | |
z_start(i); | |
} else { | |
int k = i - L; | |
int pre_l = z[k] + i; | |
if (pre_l > R) { | |
z_start(i); | |
} else { | |
z[i] = z[k]; | |
} | |
} | |
} | |
for (int i = 0; i < n; i++) { | |
printf("%d ", z[i]); | |
} | |
puts(""); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment