Cod sursa(job #2808326)

Utilizator DordeDorde Matei Dorde Data 24 noiembrie 2021 21:46:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string A , B;
int z [(int)4e6 + 5] , ans [1001];
int main()
{
    fin >> A >> B;
    B = A + '|' + B;
    int l , r;
    l = r = 0;
    for(int i = 1 ; i < B.size () ; ++ i){
        if (i <= r)
            z [i] = min (z [i - l] , r - i + 1);
        while (i + z [i] < B.size () && B [z [i]] == B [i + z [i]])
            ++ z [i];
        if (i + z [i] - 1 > r){
            r = i + z [i] - 1;
            l = i;
        }
    }
    int cnt (0);
    for(int i = A.size () + 1 ; i < B.size (); ++ i)
        if (z [i] == A.size ()){
            ++ cnt;
            if (cnt <= 1000)
                ans [cnt] = i - A.size () - 1;
        }
    fout << cnt << '\n';
    for(int i = 1 ; i <= cnt ; ++ i)
        fout << ans [i] << ' ';
    return 0;
}