Cod sursa(job #2063186)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 11 noiembrie 2017 10:05:07
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;
string p,txt;
int lp[1000];
vector <int> sol;
void patern()
{
    int l=p.size();
    int k=0;
    for(int i=1;i<l;i++)
    {
        if(p[k]==p[i])
        {
            lp[i]=++k;
        }
        else
        {
            k--;
            while(k>0)
            {
                k=lp[k];
                if(p[k]==p[i])
                {
                    lp[i]=++k;
                    break;
                }
                else
                    k--;
            }
            if(k<0)
            k=0, lp[i]=0;
        }
        //cout<<lp[i]<<" ";
    }
}
void solve()
{
    int lt=txt.length();
    int l=p.length();
    int k=0, i=0;
    while(i<lt)
    {
        if(txt[i]==p[k])
            ++k, ++i;

        if(k==l)
        {
            if(sol.size()<1000)
                sol.push_back(i-l), k=lp[k-1];
            else
                break;
        }
        else if(i<lt && p[k]!=txt[i])
        {
            if(k>0)
            {
                k=lp[k-1];
            }
            else
                ++i;
        }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    getline(cin,p);
    getline(cin,txt);
    patern();
    solve();
    cout<<sol.size()<<"\n";
    for(int i: sol)
        cout<<i<<" ";

    return 0;
}