Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- void form_suffix_array(std::vector<int>& pi, std::string& a) {
- int j = 0, i = 1;
- while (i < a.length()) {
- if (a[i] != a[j]) {
- if (j == 0 && pi[i] == 0) {
- ++i;
- } else {
- j = pi[j - 1];
- }
- } else {
- pi[i] = j + 1;
- ++i;
- ++j;
- }
- }
- }
- std::vector<int> kmp(std::string& a, std::string& t, std::vector<int>& pi) {
- std::vector<int> res;
- int n = a.length();
- int m = t.length();
- int i = 0, j = 0;
- while(i < n){
- if (a[i] == t[j]) {
- ++i; ++j;
- if (j == m) {
- res.push_back(i - m);
- }
- } else {
- if (j > 0) {
- j = pi[j - 1];
- } else{
- ++i;
- }
- }
- }
- if (res.size() == 0) {
- res.push_back(-1);
- }
- return res;
- }
- int main() {
- std::string p;
- std::cin >> p;
- std::string t;
- std::cin >> t;
- std::vector<int> pi(p.length(), 0);
- form_suffix_array(pi, p);
- std::vector<int> res = kmp(t, p, pi);
- for (int i = 0; i < res.size(); ++i) {
- if (i < res.size() - 1)
- std::cout << res[i] << ',';
- else
- std::cout << res[i];
- }
- std::cout << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement