Cod sursa(job #2336681)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 5 februarie 2019 13:54:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>
#include <cstring>
using namespace std;
char b[2000005];
int p[2000005];
char a[2000005];
int m;
void formPrefix(){
    m=strlen(a+1);
    int i=0;
    p[1]=0;
    for(int j=2; j<=m; ++j){
        while(i>0 && a[i+1]!=a[j])
            i=p[i];
        if(a[i+1]==a[j])
            ++i;
        p[j]=i;
    }
}
int n, nr;
int afis[1005];
void stringMatching()
{
    n=strlen(b+1);
    int k=0;
    for(int i=1;i<=n;i++)
    {
        while(k && b[i]!=a[k+1])
            k=p[k];
        if(b[i]==a[k+1])
            k++;
        if(k==m)
        {
            nr++;
            if(nr<=1000)
                afis[nr]=i-m;
            k=p[k];
        }
    }
}


int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n",a+1);
    scanf("%s",b+1);
    formPrefix();
    stringMatching();
    int aa=nr;
    printf("%d\n",aa);
    if(aa>=1000)
        aa=1000;
    for(int i=1; i<=aa; i++)
    {
        printf("%d ",afis[i]);
    }
    return 0;
}