Cod sursa(job #1823018)

Utilizator jason2013Andronache Riccardo jason2013 Data 5 decembrie 2016 20:01:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<bits/stdc++.h>
#define NMax 2000005

using namespace std;

int urm[NMax], v[NMax];
char P[NMax], T[NMax];
int n, m, l, y;

void Urmatorul(char *P);

int main()
{
    int i, x = -1;
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s", P+1);
    scanf("%s", T+1);
    n = strlen(T+1);
    m = strlen(P+1);

    Urmatorul(P);

    int k = 0;
    for(int i = 1; i <= n; i++)
    {
        while(k>0 && P[k+1] != T[i]) k = urm[k];
        if(P[k+1] == T[i]) k++;
        if(k == m)
            v[++y] = i-m;
    }

    printf("%d\n", y);

    for(int i=1;i<=min(y,1000);i++) printf("%d ",v[i]);
    printf("\n");
    return 0;
}


void Urmatorul(char *P)
{
    int j = 0, x;
    urm[1] = 0;
    for(int x = 2; x <= m; x++)
    {
        while(j>0 && P[j+1] != P[x]) j = urm[j];
        if(P[j+1] == P[x]) j++;
        urm[x] = j;
    }
}