Cod sursa(job #1402649)

Utilizator CosminAlexCojocaruCojocaru Cosmin CosminAlexCojocaru Data 26 martie 2015 18:21:14
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
//ifstream f("date.in");
//ofstream g("date.out");
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long int i,m,p[2000005],q,n,c,u,j[2000005],nr;
string sir,subsir;
char a,v[2000005],v1[2000005];
void prelucrare()
{
    q=0;
    p[1]=0;
    for(i=2;i<=m+1;++i)
    {
        while(q && v1[q+1]!=v[i-1])
            q=p[q];
        if(v1[q+1]==v[i-1])
            q++;
        p[i]=q;
 if(p[i]==n) c++;

    }

}
void citire()
{
    getline(f,subsir);
    getline(f,sir);
    n=subsir.size();
    m=sir.size();
    for(i=1;i<=m;++i)
    {

        v[i]=sir[i-1];
    }
     for(i=1;i<=n;i++)
        v1[i]=subsir[i-1];
}
void partea_a_2_a()
{
    for(i=1;i<=m;i++)
        if(p[i]==n) g<<i-n<<" ";
           //c++;
}
int main()
{

   citire();
   prelucrare();
   //scriere();


    g<<c;
    g<<endl;
    partea_a_2_a();

}