Cod sursa(job #2721175)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 11 martie 2021 16:56:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <vector>

const int MAXN = 2e6 + 1;

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

string a,b;
string s;
int z[MAXN];

void zalgorithm(){
    int n = s.size();
    int r = -1;
    int l = -1;
    for(int i = 1; i < n; i++){
        if(i > r){
            int k = 0;
            while(i + k < n && s[i + k] == s[k]){
                k++;
            }
            l = i;
            r = i + k - 1;
            z[i] = k;
        }else{
            if(s[i] != s[0]){
                z[i] = 0;
            }else{
                int defazaj = i - l;
                int initial = min(z[defazaj],r - i + 1);
                int start = i + initial;
//                defazaj++;
                int k = 0;
//                cout<<defazaj<<" "<<initial<<" "<<s[start]<<" "<<s[k + initial]<<endl;
                while(start + k < n && s[start + k] == s[k + initial])
                    k++;
                l = i;
                r = start + k - 1;
                z[i] = initial + k;
            }
        }
    }
//    cout<<s.size()<<" "<<n<<endl;
//    for(auto c : s)
//        cout<<c<<" ";
//    cout<<endl;
//    for(int i = 0; i < s.size(); i++){
//        cout<<z[i]<<" ";
//    }
//    cout<<endl;
    vector<int>aparitii;
    for(int i = a.size() + 1; i < n; i++){
        if(z[i] >= a.size()){
//            cout<<i - a.size() - 1<<" ";
            aparitii.push_back(i - a.size() - 1);
        }
    }
    out<<aparitii.size()<<'\n';
    int sz = aparitii.size();
    for(int i = 0; i < min(1000,sz); i++)
        out<<aparitii[i]<<" ";
}

int main()
{
    in>>a>>b;
    s = a + '#' + b;
    zalgorithm();
    return 0;
}