Cod sursa(job #1254627)

Utilizator andreiagAndrei Galusca andreiag Data 3 noiembrie 2014 02:49:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <string.h>

using namespace std;
const int Nmax = 2000666;

string A, B;
int T[Nmax];
vector<int> sol;

void preprocess(string &A)
{
    int N = A.length();
    T[0] = -1;
    T[1] = 0;
    for(int i = 2; i <= N; i++)
    {
        int j = i-1;
        while(T[j] > -1)
        {
            if (A[i-1] == A[T[j]]) {
                T[i] = T[j] + 1;
                break;
            } else {
                j = T[j];
            }
        }
    }
}

int main()
{
    ifstream f ("strmatch.in");
    ofstream g ("strmatch.out");
    
    f >> A >> B;
    int N = A.length();
    int M = B.length();
    
    preprocess(A);

    int m = 0, i = 0;
    while(m+N <= M) {
        if (B[m+i] == A[i])
        {
            i++;
            if (i == N)
            {
                sol.push_back(m);
                int j = T[i];
                m += i - j;
                i = j > 0 ? j : 0;
            }
        }
        else
        {
            int j = T[i];
            m += i - j;
            i = j > 0 ? j : 0;
        }
    }
    
    g << sol.size() << '\n';
    for (size_t i = 0; i < 1000 && i < sol.size(); i++)
        g << sol[i] << ' ';
    g << '\n';

    return 0;
}