Cod sursa(job #1879992)

Utilizator sfechisalin@yahoo.comSfechis Alin [email protected] Data 15 februarie 2017 12:24:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define NN 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[NN],B[NN];
int main()
{
    fin.getline(B,NN);
    fin.get(A,NN);
    int N = strlen(B) , M = strlen(A);
    for (int i = N ; i ;--i) B[i] = B[i-1];B[0] = ' ';
    for (int i = M ; i ;--i) A[i] = A[i-1];A[0] = ' ';
    int k = 0;
    vector<int> answ;
    vector<int>pi(N,0);
    for(int i = 2; i <= N; ++i)
    {
        while (k && B[k+1] != B[i])
            k = pi[k];
        if (B[k+1] == B[i])
            k++;
        pi[i] = k;
    }

    k = 0;
    for (int i = 1; i <= M; ++i)
    {
        while(k && B[k+1] != A[i])
            k = pi[k];
        if (B[k+1] == A[i])
            k++;
        if (k == N)
        {
            answ.push_back(i-N);
            k = pi[k];
        }
    }
    int len = ( (answ.size()>1000)?1000:answ.size() );
    fout << len << '\n';
    for (int i = 0 ;i < len ;++i)
        fout << answ[i] << ' ';
    return 0;
}