Cod sursa(job #2223368)

Utilizator PescaruVictorPescaru Victor PescaruVictor Data 19 iulie 2018 22:28:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
//#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>

using namespace std;

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

int lgA, lgB, ap;
char a[2000010], b[2000010];
int t[2000010], v[1005];
int main()
{
    int act=0, urm;
    cin>>a>>b;
    lgA=strlen(a);
    lgB=strlen(b);

    act = 0;
    urm = 1;
    t[0] = -1;


    while(urm <= lgA)
    {
        if(a[act] == a[urm])
        {
            t[urm] = t[act];
            ++act;
            ++urm;
        }
        else
        {
            t[urm] = act;
            do
                act = t[act];
            while(act >= 0 && a[act] != a[urm]);

            ++act;
            ++urm;
        }
    }

    for(int i=0, j=0; j<lgB; )
    {
        if(a[i] == b[j])
        {
            ++i;
            ++j;
            if(i == lgA)
            {
                ++ap;
                if(ap <= 1000)
                    v[ap] = j-lgA;
                i=t[i];
            }
        }
        else
        {
            i = t[i];
            if(i < 0)
            {
                ++i;
                ++j;
            }
        }
    }

    cout<<ap<<'\n';
    for(int i=1; i <= min(ap, 1000); ++i)
        cout<<v[i]<<' ';
    return 0;
}