Cod sursa(job #1415613)

Utilizator alex1096Postolache Alex alex1096 Data 5 aprilie 2015 15:50:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000002
using namespace std;
char a[NMAX],b[NMAX];
int q[NMAX],nr,v[1002];
int minim(int a, int b)
{
    if(a<b)
        return a;
    return b;
}
void citire()
{
    ifstream fin("strmatch.in");
    fin>>(a+1);
    fin>>(b+1);
}
void strmatch()
{
    int c=0,d=strlen(a+1),e=strlen(b+1);
    for(int i=2;i<=strlen(a+1);++i)
    {

        while(a[i]!=a[c+1] && c!=0)
            c=q[c];
        if(a[i]==a[c+1])
            c++;
        q[i]=c;
    }
    c=0;
    for(int i=1;i<=e;++i)
    {
        while(b[i]!=a[c+1] && c!=0)
                c=q[c];
        if(a[c+1]==b[i])
            c++;
        if(c==d)
        {
            nr++;
            if(nr<=1000)
                {
                    v[nr]=i-d;
                }
        }
    }
}
void afisare()
{
    ofstream fout("strmatch.out");
    fout<<nr<<"\n";
    for(int i=1;i<=minim(nr,1000);++i)
        fout<<v[i]<<" ";
}
int main()
{
    citire();
    strmatch();
    afisare();
    return 0;
}