Cod sursa(job #3182766)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 9 decembrie 2023 15:47:51
Problema Potrivirea sirurilor Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int z[40005];
char s[40005];
char t[20005];
vector <int> v;
int main()
{
    int n,i,j,l = 0,r = 0,cnt = 0,sz;
    fin >> s;
    n = strlen(s);
    fin.get();
    fin >> t;
    sz = n + strlen(t);
    strcat(s,t);
    for(i = 1; i < sz; i++){
        if(i > r){
            int e = 0,x = i;
            while(s[x] == s[e] && x < sz){
                x++;
                e++;
            }
            if(e){
                l = i;
                r = x - 1;
                z[l] = r - l + 1;
            }
        }
        else{
            int k = i - l;
            if(z[k] < r - i + 1) z[i] = z[k];
            else{
                int x = r,e = r - l,ok = 0;
                while(s[x] == s[e] && x < sz){
                    x++;
                    e++;
                    ok = 1;
                }
                if(ok){
                    r = x - 1;
                    l = i;
                    z[i] = r - k + 1;
                }
                else z[k] = r - k + 1;
            }
        }
        if(z[i] >= n && i >= n){
            cnt++;
            if(v.size() < 1000) v.push_back(i - n);
        }
    }
    fout << cnt << "\n";
    for(auto x : v) fout << x << " ";
    return 0;
}