Cod sursa(job #953269)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 25 mai 2013 16:52:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>

using namespace std;

    int d[200005];
    int pref[200005];
    char a[200005],b[200005];
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");

    int n1,n2,i;
    cin.get(a,200005);
    cin.get();
    cin.get(b,200005);
    n1=strlen(a);
    n2=strlen(b);

    #define pref (pref-1)
    #define a (a-1)
    #define b (b-1)

    pref[1]=0;
    int k=0;
    for(i=2;i<=n1;i++)
    {
        //k=pref[i-1];
        while(k>0 && a[k+1]!=a[i])
            k=pref[k];
        if(a[k+1]==a[i])
            k++;
        pref[i]=k;
    }
//cout<<"da"<<endl;
    int poz=0;
    k=0;
    for(i=1;i<=n2;i++)
    {
        while(k>0 && a[k+1]!=b[i])
            k=pref[k];
        if(a[k+1]==b[i])
            k++;
        if(k==n1)
        {
            d[poz++]=i-n1;
            k=pref[k];
        }
    }
    cout<<poz<<'\n';
    if(poz>1000)
        poz=1000;
    for(i=0;i<poz;i++)
        cout<<d[i]<<' ';
    cout<<'\n';
    cin.close();
    cout.close();
    return 0;
}