Cod sursa(job #2399249)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 7 aprilie 2019 10:56:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <string>
#include <vector>

using namespace std;

string pattern, text;

int lps[2000004];
vector <int> ans;

int main() {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    cin >> pattern;
    cin >> text;

    int len = 0;
    int i = 1;
    lps[0] = 0;

    while(i < pattern.size())
    {
        if(pattern[i] == pattern[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else {
            if(len != 0) {
                len = lps[len - 1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }

    i = 0;
    int j = 0;

    while(i < text.size())
    {
        if(pattern[j] == text[i])
        {
            ++i;
            ++j;
        }

        if(j == pattern.size())
        {
            ans.push_back(i - j);
            j = lps[j - 1];
        }

        else if(i < text.size() && pattern[j] != text[i]) {
            if(j) j = lps[j - 1];
            else {
                i++;
            }
        }
    }

    cout << ans.size() << '\n';

    int cnt = 0;
    for(auto x: ans) {
        if(cnt == 1000) break;
        cnt++;
        cout << x << ' ';
    }

    return 0;
}