Cod sursa(job #601293)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 5 iulie 2011 20:38:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <string>

#define NMax 2000005

using namespace std;

char N[NMax], M[NMax];
int n, m, pi[NMax], Match[1005], NMatch;

void Read ()
{
    ifstream fin ("strmatch.in");
    fin >> N >> M;
    n=strlen (N);
    for (int i=n; i>0; --i)
    {
        N[i]=N[i-1];
    }
    N[0]='0';
    m=strlen (M);
    for (int i=m; i>0; --i)
    {
        M[i]=M[i-1];
    }
    M[0]='0';
    fin.close ();
}

inline int Min (int a, int b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}

void Print ()
{
    ofstream fout ("strmatch.out");
    fout << NMatch << "\n";
    for (int i=0; i<Min (NMatch, 1000); ++i)
    {
        fout << Match[i] << " ";
    }
    fout << "\n";
    fout.close ();
}

void CalculPrefix ()
{
    int k=0;
    pi[1]=0;
    for (int i=2; i<=n; ++i)
    {
        while (k>0 and N[k+1]!=N[i])
        {
            k=pi[k];
        }
        if (N[k+1]==N[i])
        {
            k++;
        }
        pi[i]=k;
    }
}

void KMP ()
{
    int q=0;
    CalculPrefix ();
    for (int i=1; i<=m; ++i)
    {
        while (M[i]!=N[q+1] and q>0)
        {
            q=pi[q];
        }
        if (N[q+1]==M[i])
        {
            q++;
        }
        if (q==n)
        {
            if (NMatch<1000)
            {
                Match[NMatch++]=i-n;
            }
            else
            {
                NMatch++;
            }
        }
    }
}

int main()
{
    Read ();
    KMP ();
    Print ();
    return 0;
}