Cod sursa(job #2595958)

Utilizator k2e0e0w3qDumitrescu Gheorghe k2e0e0w3q Data 8 aprilie 2020 19:51:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define N 2100005
#define LIM 1000
using namespace std;

char s[N], t[N];
long long pi[N];
void compute () {
    long long i=1, len=0;
    while (t[i])
        if (t[i]==t[len])
            pi[i++]=++len;
        else
            if (len)
                len=pi[len-1];
            else
                pi[i++]=0;
}

int main () {
    ifstream fin ("strmatch.in");
    ofstream fout ("strmatch.out");
    vector <long long> ans;

    fin >> t >> s;
    compute();

    long long i=0, j=0;
    while (s[i] && ans.size()!=LIM)
        if (s[i]==t[j]) {
            ++i, ++j;
            if (!t[j]) {
                ans.push_back(i-j);
                j=pi[j-1];
            }
        }
        else
            if (j)
                j=pi[j-1];
            else
                ++i;

    fout << ans.size() << '\n';
    for (auto it: ans)
        fout << it << ' ';
    return 0;
}