Cod sursa(job #1076679)

Utilizator ThomasFMI Suditu Thomas Thomas Data 10 ianuarie 2014 14:54:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <cstring>
using namespace std;

#define Nmax 2000001

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[Nmax],B[Nmax];
int m,n,pr;
int P[Nmax];
int nr,sol[1002];

void pref(int x)
{
    int i,k=-1;
    for(i=1;i<x;i++)
    {
        while(k>0 && A[k+1]!=A[i]) k=P[k];
        if(A[i]==A[k+1]) k++;
        P[i]=k;
    }
}

int smatch()
{
    int i,x=-1;
    for(i=0;i<n;i++)
    {
        while(x>0 && A[x+1]!=B[i]) x=P[x];
        if(A[x+1]==B[i]) x++;
        if(x==m-1)
        {
            nr++;
            if(nr<=1000) sol[nr]=i-m+1;
            x=P[x];
        }
    }
}

int main()
{
    int i;

    f>>A>>B;
    m=strlen(A);
    n=strlen(B);

    pref(m);
    smatch();

    g<<nr<<"\n";
    for(i=1;i<=nr;i++) g<<sol[i]<<" ";
    g<<"\n";

    f.close();
    g.close();
    return 0;
}