Cod sursa(job #2201773)

Utilizator FlaviusFeteanFetean Flavius FlaviusFetean Data 5 mai 2018 22:51:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <cstring>

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

char A[2000005], B[2000005];
int N, M, P[2000005],v[1005];

void prep()
{
    int i, k = 0;

    for(i = 1; i < M; i++)
    {
        if(A[i] == A[k]) k++;
        else {
        k = 0; if(A[i] == A[k]) k++;
        }P[i] = k;
    }
}

int main()
{
    int i, k = 0;

    fin.getline(A,2000005); M = strlen(A);
    fin.getline(B,2000005); N = strlen(B);

    prep();

    for(i = 0; i < N; i++)
    {
        while( k != 0 && (A[k] != B[i]) )
            k = P[max(k - 1, 0)];
        if( A[k] == B[i] ) k++;

        if(k == M)
        {
            v[min(++v[0],1001)] = i - M + 1;
            k = P[M - 1];
        }
    }

    fout << v[0] << "\n";

    for(i = 1; i <= min(v[0],1000); i++) fout << v[i] << " ";

    return 0;
}