Cod sursa(job #2595956)

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

char s[N], t[N];
int pi[N];
void compute () {
    int 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 <int> ans;

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

    int 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;
}