Cod sursa(job #2353601)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 24 februarie 2019 13:30:35
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

string a, b;
int lp[2000005], la, lb;
vector <int> sol;
char *p;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    getline(cin,a);
    getline(cin,b);

    la=a.length();
    lb=b.length();
    int k=0;
    for(int i=1 ; i<la; ++i){
        if(a[k]==a[i])
            lp[i] = ++k;
        else{
            --k;
            //k=lp[k];
            while(k>=0){
                k=lp[k];
                if(a[k]==a[i]){
                    lp[i]=++k;
                    break;
                }
                --k;
            }
            if(k<0)
                lp[i]=0, k=0;
        }
    }

    k=0;
    for(int i=0;i<lb;++i){
        if(k==la){
            sol.push_back(i-la);
            k=lp[k-1];
        }
        if(a[k]==b[i])
            ++k;
        else{
            k--;
            while(k>0){
                k=lp[k];
                if(a[k]==b[i]){
                    ++k;
                    break;
                }
                --k;
            }
            if(k<0)
                k=0;
        }
    }
    if(k==la){
        sol.push_back(lb-la);
    }

    /*
    for(int i=0;i<la;++i)
        cout<<lp[i]<<" ";
    */

    la = sol.size();
    cout<<la<<"\n";

    la = min(la,1000);

    for(int i = 0; i < la; ++i)
        cout<<sol[i]<<" ";

    return 0;
}