Cod sursa(job #1887304)

Utilizator dumitrescugeorgeGeorge Dumitrescu dumitrescugeorge Data 21 februarie 2017 15:14:27
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <cstdio>
#include <cstring>
using namespace std;
char s1[2000010],s[2000010];
int prefix[2000010],n,m,q=0,x=0,pos[10000],ok=0,ok1=0;
void citire()
{
    fgets(s1,2000010,stdin);
    fgets(s,2000010,stdin);
    s1[strlen(s1)-1]=0;
    s[strlen(s)-1]=0;
    m=strlen(s1);
    n=strlen(s);
}
void prefix1()
{
    prefix[0]=0;
    int i=0,j=1;
    while(j<=m-1)
    {
        if(s1[i]==s1[j])
        {
            prefix[j]=prefix[j-1]+1;
            i++;
        }
        else
            while(i>0&&s1[i]!=s1[j])
        {
            i=prefix[i-1];
            ok=1;
        }
        if(ok==1&&i!=0)
            prefix[j]=prefix[i+1]+1;
            if(i==0)
                prefix[j]=0;
            j++;
        ok=0;
    }
}
void cerinta()
{
    int j=0,l=0,i=0,nr=0;
    while(i<=n-1)
    {
        while(s1[j]==s[i]&&i<=n-1)
            {
                i++;
                j++;
                l++;
            }
        if(l==m)
        {
            nr++;
        }
        if(s1[i]!=s[j])
        {
            while(j!=0&&s1[j]!=s[i])
            {
                j=prefix[j-1];
                ok1=1;
            }
        }
        l=j;
        if(ok1==0)
            i++;
        ok1=0;
    }
    printf("%d\n",nr);
    if(nr>1000)
        nr=1000;
    j=0;
    l=0;
    i=0;
       while(i<=n-1&&nr!=0)
    {
        while(s1[j]==s[i]&&i<=n-1)
            {
                i++;
                j++;
                l++;
            }
        if(l==m)
        {
            nr--;
            printf("%d %d\n",i-l,i-1);
        }
        if(s1[i]!=s[j])
        {
            while(j!=0&&s1[j]!=s[i])
            {
                j=prefix[j-1];
                ok1=1;
            }
        }
        l=j;
        if(ok1==0)
            i++;
        ok1=0;
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    citire();
    prefix1();
    cerinta();
    //cout << "Hello world!" << endl;
    return 0;
}