Cod sursa(job #1824772)

Utilizator jordan1998Jordan jordan1998 Data 8 decembrie 2016 13:42:56
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000005],b[2000005];
int lga,lgb,i,p[2000005],pos,n,x,t[1005];
int main()
{
    f>>a+1>>b+1;
    lga=strlen(a+1);
    lgb=strlen(b+1);
    x=0;
    for (i = 2; i <= lga; ++i)
    {
        while (x && a[x+1] != a[i])
            x = p[x];
        if (a[x+1] == a[i])
            ++x;
        p[i] = x;
    }
  // g<<p[3];
x=0;
for(i=1;i<=lgb;i++)
{  while (x && a[x+1] != b[i])
            x = p[x];
     if (a[x+1] == b[i])
            ++x;
    if(x==lga)
        {
            ++n;
            x=p[x];
            if(n<=1000)
                p[n]=i-lga;
        }
}
 g<<n<<"\n";
    if(n>1000)
        n=1000;
    for(i=1;i<=n;++i)
        g<<p[i]<<" ";
    f.close();
    g.close();
    return 0;

}