Cod sursa(job #1915398)

Utilizator dumitrescugeorgeGeorge Dumitrescu dumitrescugeorge Data 8 martie 2017 20:54:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <cstring>
using namespace std;
char s1[2000010],s[2000010];
int prefix[2000010],n,m,q=0,x=0,pos[2000010],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()
{
    int i=0,j=1;
    while(j<=m-1)
    {
        if(s1[i]==s1[j])
        {
            prefix[j]=i+1;
            i++;
            j++;
        }
        else if(i!=0)
        {
            i=prefix[i-1];
        }
        else
            j++;
    }
}
void cerinta()
{
    int j=0,i=0;
    while(i<=n-1)
    {
        if(s[i]==s1[j])
        {
            i++;
            j++;
            if(j==m)
            {
                pos[0]++;
                if(pos[0]<=1000)
                    pos[pos[0]]=i-m;
            }
        }
        else
            if(j)
        {
            j=prefix[j-1];
        }
        else
            i++;
    }
    if(pos[0]>1000)
        pos[0]=1000;
    printf("%d\n",pos[0]);
    for(int i=1;i<=pos[0];i++)
        printf("%d ",pos[i]);
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    citire();
    prefix1();
    cerinta();
    //cout << "Hello world!" << endl;
    return 0;
}