Cod sursa(job #2616188)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 16 mai 2020 21:35:08
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>

const int MAXN = 4e6 + 4;

using namespace std;

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

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

void Z(){
    int n = s.size();
    int l = 0,r = 0;
    int cnt = 0;
    z[0] = s.size();
    for(int i = 1; i < n; i++){
        if(i > r){
            int cnt = 0;
            while(i + cnt < n && s[i + cnt] == s[cnt])
                cnt++;
            z[i] = cnt;
            l = i;
            r = i + cnt - 1;
        }else{
            if(z[i - l] + i > r){
                z[i] = z[i - l];
            }else{
                z[i] = min(z[i - l],r - i + 1);
                int capat = i + z[i],cnt = 0;
                int inceput = z[i];

                while(capat + cnt < n && s[capat + cnt] == s[cnt + inceput])
                    cnt++;
                z[i] += cnt;
                l = i;
                r = capat + cnt;
            }
        }
        if(z[i] == a.size()){
            if(cnt + 1 <= 1000)
                cnt++;
        }
    }
    out<<cnt<<"\n";
    for(int i = 0; i < n; i++){
        if(z[i] == a.size() && cnt){
            cnt--;
            out<<i - a.size() - 1<<" ";
        }
    }
}

int main()
{

    in>>a>>b;
    s = a + '#' + b;
    //cout<<s<<endl;
    Z();
    return 0;
}