Cod sursa(job #1915517)

Utilizator deepsterescuCraciunescu Denis Bogdan deepsterescu Data 8 martie 2017 21:23:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;
char s[2000005],t[2000005];
int n,m,i,j,b[1000005],nr;

queue<int> q;

void prep()
{
    i = 0; j=-1; b[0] = -1;
    while (i < n)
    {
        while (j>=0 && s[j] != s[i]) j = b[j];
        i++; j++;
        b[i] = j;
    }
}

void caut()
{
    i = 0; j = 0;
    while (i <m)
    {
        while (j>=0 && t[i] != s[j]) j = b[j];
        j++; i++;
        if (j == n)
        {
            nr++;
            q.push(i-j);
            j = b[j];
        }
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",&s); n = strlen(s);
    scanf("%s",&t); m = strlen(t);
    nr = 0;
    prep();
    caut();
    printf("%d\n",nr);
    while (!q.empty())
    {
        printf("%d ",q.front()); q.pop();
    }
}