Cod sursa(job #1814923)

Utilizator DobosDobos Paul Dobos Data 24 noiembrie 2016 17:52:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define NMAX  2000005
#define SMAX 1005
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string A,B;
int P[NMAX],S[SMAX];

inline void make_prefix(){
    int q = 0;
    for(int i = 2; i <= A.size(); i++){
        while(q && A[q + 1] != A[i])
            q = P[q];
        if(A[q + 1] == A[i])
            q++;
        P[i] = q;
    }
}



int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    fin >> A >> B;

    A = ' ' + A;
    B = ' ' + B;

    make_prefix();
    int q = 0,m = A.size() - 1,n = 0;
    for(int i = 1; i <= B.size(); i++){

        while(q && A[q + 1] != B[i])
            q = P[q];
        if(A[q + 1] == B[i])
            q++;
        if(q == m){
            q = P[q];
            n++;
            if(n <= 1000)
                S[n] = i - m;
        }

    }
    fout << min(n,1000) << "\n";
    for(int i = 1; i <= min(n,1000); i++)
        fout << S[i] << " ";

    return 0;
}