Cod sursa(job #2028052)

Utilizator NicuBaciuNicu Baciu NicuBaciu Data 27 septembrie 2017 08:24:44
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <string>

using namespace std;

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

string a, b;
int p[2000001];
int sol[2000001];
void pref(string a);

int main()
{
    fin >> a >> b;

    pref(a);

    int ct=0;

    for(int i=0; i<b.size(); i++)
    {
        bool sem=true;

        for(int j=0; j<a.size() && sem; j++)
        {
            if(b[i+j]!=a[j])
            {
                if(p[j]!=0)
                {
                    i+=j-p[j];
                    sem=false;
                }
            }
        }

        if(sem)
        {
            sol[ct]=i;
            ct++;
        }
    }

    fout << ct << '\n';

    for(int i=0; i<ct; i++)
        fout << sol[i] << " ";

    return 0;
}

void pref(string a)
{
    for(int i=1; i<a.size(); i++)
    {
        int j=p[i-1];

        while(j>0 && a[i]!=a[j])
            j=p[j-1];

        if(a[i]==a[j])
            j++;

        p[i]=j;
    }
}