Cod sursa(job #1504919)

Utilizator GuzgleteBumbu Alexandru Guzglete Data 18 octombrie 2015 16:02:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

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

char p[2000010],s[2000010];
int pref[2000010],rez[1010];
int i,j,k,nr,n,m;

void prefix (int n)
{
    pref[0]=0;
    i=0;
    for (j=1;j<n;j++)
    {
        while (i>0 && p[i]!=p[j])
            i=pref[i];
        if (p[i]==p[j])
            i++;
        pref[j]=i;
    }
}

void rezultat (int n, int m)
{
    i=0;
    j=0;
    k=0;
    while (n-k>=m-1)
    {
        while (j<=m-1 && s[i]==p[j])
        {
            i++;
            j++;
        }
        if (j>m-1)
        {
            nr++;
            rez[nr]=k;
        }
        if (pref[j-1]>0)
            k=i-pref[j-1];
        else
        {
            if (i==k)
                i++;
            k=i;
        }

        if (j>0)
            j=pref[j-1];
    }
}

int main()
{
    fin.getline (p,2000010);
    fin.getline (s,2000010);

    n=strlen(p);
    prefix(n);
    n=strlen(s);
    m=strlen(p);
    rezultat(n,m);
    fout<<nr<<"\n";
    i=1;
    while (i<=nr && i<=1000)
    {
        fout<<rez[i]<<" ";
        i++;
    }
    return 0;
}