Cod sursa(job #2136883)

Utilizator radurotaruRotaru Radu Stefan radurotaru Data 20 februarie 2018 12:59:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char aa[2000001], cc[2000001];
int v[1001],e,r;
void barray( char *a, int m, int *b)
{
    int q=0;
    b[0]=0;
    int i=1;
    while(i<m)
    {
        if(a[i]==a[q])
        {
            q++;
            b[i]=q;
            i++;
        }
        else
        {
            if(q!=0)
            {
                q=b[q-1];
            }
            else
            {
                b[i]=0;
                i++;
            }
        }
    }
}
void KMP( char *a, char *c)
{
    int m=strlen(a);
    int n=strlen(c);
    int b[m];
    barray(a,m,b);
    int i=0;
    int j=0;
    while(i<n)
    {
        if(a[j]==c[i])
        {
            i++;
            j++;
        }
        if(j==m)
        {
            e++;
            if(e<=1000)
            {
                r++;
                v[r]=i-j;
            }
            j=b[j-1];
        }
        else if(i<n && a[j]!=c[i])
        {
            if(j!=0)
            j=b[j-1];
            else
            i++;
        }
    }
}
int main()
{
    f>>aa;
    f>>cc;
    KMP(aa,cc);
    g<<e<<endl;
    if(e>1000)
    e=1000;
    for(int i=1;i<=e;i++)
    {
        g<<v[i]<<" ";
    }
    return 0;
}