Cod sursa(job #2335628)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 4 februarie 2019 13:04:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstring>
#include <cstdio>
using namespace std;

char a[2000005];
int p[2000005];

char b[2000005];
int m;
void constrPrefix()
{
    m=strlen(a+1);
    p[1]=0;
    int i=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 afis[1005], nr;
void stringMatching()
{
    int k=0;
    int n=strlen(b+1);
    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);
    constrPrefix();
    stringMatching();
    printf("%d\n",nr);
    int aa=nr;
    if(nr>1000)
        aa=1000;
    for(int i=1; i<=aa; i++)
        printf("%d ",afis[i]);
    return 0;
}