Cod sursa(job #1414099)

Utilizator robertstrecheStreche Robert robertstreche Data 2 aprilie 2015 12:48:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <cstring>
#include <queue>

#define LIM 1000
#define LMAX 2000005

using namespace std;

int nr_sol,phi[LMAX];
char S1[LMAX],S2[LMAX];

queue <int>sol;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s",S1+1,S2+1);
    int k=0;
    int l1=strlen(S1+1);
    int l2=strlen(S2+1);

    for (int i=2;i<=l1;i++)
    {
        while (k && S1[k+1]!=S1[i])k=phi[k];
        if (S1[k+1]==S1[i])k++;
        phi[i]=k;
    }
    k=0;
    for (int i=1;i<=l2;i++)
    {
        while (k && S1[k+1]!=S2[i])k=phi[k];
        if (S1[k+1]==S2[i])k++;
        if (k==l1)sol.push(i-l1);
    }
    printf("%d\n",sol.size());
    for (int x=1000;x && !sol.empty();sol.pop(),x--)
     printf("%d ",sol.front());

    fclose(stdin);
    fclose(stdout);
}