Cod sursa(job #1364496)

Utilizator edi4ever4Agarici Eduard edi4ever4 Data 27 februarie 2015 18:15:01
Problema Potrivirea sirurilor Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <cstring>
using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
char s[2000002],t[2000002];
int pi[2000002],d[2000002],m,n,nr,poz[1005];
void Citire()
{
    fscanf(f,"%s",&t);
    fscanf(f,"%s",&s);
    n=strlen(s);
    m=strlen(t);
}
void Precalculare()
{
    int i,k=0;
    pi[0]=0;
    for(i=1; i<m; i++)
    {
        if(t[i]==t[k]) k++;
        else
        {
            while(k>0 && t[k]!=t[i])
                k=pi[k-1];
            if(t[k]==t[i]) k++;
        }
        pi[i]=k;
    }
}
void KMP()
{
    int i,k=0;
    for(i=0; i<n; i++)
        if(s[i]==t[i]) k++;
        else
        {
            while(k>0  && t[k]!=s[i])
                k=pi[k-1];
            if(t[k]==s[i]) k++;
            d[i]=k;
            if(k==m)
            {
                nr++;
                if(nr<=1000)
                    poz[nr]=i-m+1;
            }
        }
}
void Afisare()
{int i;
 fprintf(g,"%d\n",nr);
 if(nr<=1000)
     for(i=1;i<=nr;i++)
        fprintf(g,"%d ",poz[i]);
 else
     for(i=1;i<=1000;i++)
        fprintf(g,"%d ",poz[i]);
}
int main()
{
    Citire();
    Precalculare();
    KMP();
    Afisare();
    fclose(f);
    fclose(g);
    return 0;
}