Mai intai trebuie sa te autentifici.

Cod sursa(job #2791203)

Utilizator andreea13gaftonGafton Andreea andreea13gafton Data 30 octombrie 2021 10:58:43
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <cstring>
#include <cstdio>

#define NMAX 2000001
#define MOD1 66660613
#define MOD2 77773013
using namespace std;

char s1[NMAX], s2[NMAX];
long long l1, l2;
int nr, a[1005], p[100005];

void citire()
{
    scanf("%s\n%s", s1, s2);
    l1=strlen(s1);
    l2=strlen(s2);
}

void prefix()
{
    int j=-1, i=0;
    p[0]=-1;
    while(i<l1)
    {
        while(j>=0 && s1[i]!=s1[j])
            j=p[j];
        j++;
        i++;
        p[i]=j;
    }
}

void kmp()
{
    int j=0, i=0;
    while(i<l2)
    {
        while(j>=0 && s2[i]!=s1[j])
            j=p[j];
        j++;
        i++;
        if(j==l1)
        {
            j=p[j];
            nr++;
            if(nr<=1000)
            a[nr]=i-l1;

        }
    }
}


void afisare()
{
    printf("%d\n", nr);
    for(int i=1; i<=(nr<=1000?nr:1000); ++i)
    printf("%d ", a[i]);
}


int main()
{
    freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
    citire();
    prefix();
    kmp();
    afisare();
    return 0;

}