Cod sursa(job #947306)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 7 mai 2013 09:41:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
///gasirea numarului de aparitii a sirului a in sirul b
#include <fstream>
#include <cstring>
#define In "strmatch.in"
#define Out "strmatch.out"
#define Nmax 2000010
using namespace std;
char A[Nmax],B[Nmax];
int pi[Nmax],sol[Nmax],n,m;//(pi[i]<i)
//pi[i] = k,k este lungimea celui mai lung prefix a lui Ai(prefix de lungime i lui A)
//egal cu sufixul de lungime k a lui Ai
inline void Citire()
{
    ifstream f(In);
    f>>(A+1)>>(B+1);
    n = strlen(A+1);
    m = strlen(B+1);
    f.close();
}
inline void Prefix()
{
    int i,ind = 0;
    pi[1] = 0;
    for(i=2;i<=n;i++)
    {
        while(ind>0 && A[ind+1]!=A[i])
            ind = pi[ind];
        if(A[ind+1]==A[i])
            ind++;
        pi[i] = ind;
    }
}
inline void KMP()
{
    int i,ind = 0;
    for(i=1;i<=m;i++)
    {
        while(ind>0 && A[ind+1]!=B[i])
            ind = pi[ind];
        if(A[ind+1]==B[i])
            ind++;
        if(ind==n)
        {
            ind = pi[ind];
            if(sol[0]<1000)
                sol[++sol[0]] = i;
        }
    }
}
inline void Afisare()
{
    ofstream g(Out);
    int i;
    g<<sol[0]<<"\n";
    for(i=1;i<=sol[0];i++)
        g<<sol[i]-n<<" ";
    g<<"\n";
    g.close();
}
int main()
{
    Citire();
    Prefix();
    KMP();
    Afisare();
    return 0;
}