Cod sursa(job #1577850)

Utilizator mirupetPetcan Miruna mirupet Data 23 ianuarie 2016 22:02:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<cstdio>
#include<cstring>
#include<vector>
#define DIM 2000010
#define Minim(x, y) (x <= y ? x : y)
using namespace std;

FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);

int N, M;
int k, i, p[DIM];
int v[DIM];
char S1[DIM], S2[DIM];
vector <int> sol;

int main()
    {
        gets(S1 + 1); M = strlen(S1 + 1);
        gets(S2 + 1); N = strlen(S2 + 1);

        k=0; p[1]=0;

        for (i = 2; i <= M; i++)
        {
            while (k > 0 && S1[i] != S1[k + 1])
                k = p[k];
            if (S1[i] == S1[k + 1])
                ++k;
            p[i] = k;
        }


        /*for (int i = 1; i <= M; i++)
            printf("%d ", p[i]);*/

        k = 0;
        for (int i = 1; i <= N; i++)
        {
            while (k && S2[i] != S1[k + 1])
                k = p[k];
            if (S2[i] == S1[k + 1])
                k ++;
            if (k == M)
            {
                    sol.push_back(i - M);
                    k = p[k];
            }
        }

        printf("%d\n", sol.size());

        for (int i = 0; i < Minim(sol.size(), 1000u); i++)
            printf("%d ", sol[i]);


    }