Cod sursa(job #1981472)

Utilizator Mihaibv13Mihai Stoian Mihaibv13 Data 15 mai 2017 19:53:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#include <cstring>
#define lmax 2000010
using namespace std;

char pattern[lmax];
char s[lmax];
int pref[lmax],poz[lmax],i,j,n,m,noccur=0;

int main()
{
    FILE *f=fopen("strmatch.in","r");
    fscanf(f,"%s%s",pattern,s);
    n=strlen(s);
    m=strlen(pattern);
    i=1;
    j=0;
    pref[0]=0;
    while(pattern[i])
        if(pattern[i]==pattern[j])
            pref[i++]=++j;
        else if(j==0)
            pref[i++]=0;
        else
            j=pref[j-1];
    i=0;
    j=0;
    while(s[i])
        if(s[i]==pattern[j])
        {
            ++i,++j;
            if(pattern[j]==0)
            {
                poz[++noccur]=i-m;
                j=pref[j-1];
            }
        }
        else if(j==0)i++;
        else j=pref[j-1];
    fclose(f);
    f=fopen("strmatch.out","w");
    fprintf(f,"%d\n",noccur);
    for(i=1;i<=noccur;i++)
        fprintf(f,"%d ",poz[i]);
    return 0;
}