Cod sursa(job #1133089)

Utilizator andreiagAndrei Galusca andreiag Data 4 martie 2014 13:41:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <string>
#include <stdio.h>
#include <fstream>

using namespace std;
const int Nmax = 2000005;

string A, B;
int T[Nmax];

void build(const string &S)
{
    T[0] = -1; T[1] = 0;
    int i = 2, tmp = 0; // = T[i-1];
    for (;i < S.size() + 1;) {
        if (S[tmp] == S[i-1])
            T[i++] = ++tmp;
        else if (tmp > 0)
                tmp = T[tmp];
        else T[i++] = 0;
    }
}

int main()
{
    ifstream f ("strmatch.in");
    ofstream g ("strmatch.out");

    getline(f, A);
    getline(f, B);

    int N = A.size();
    build(A);
    int m = 0, // pozitia de start in B;
        i = 0; // pozitia curenta in A;
    int cnt = 0;
    int match[1005];
    while (m + N <= B.size())
    {
        if (A[i] == B[m+i]) {
            i++;
            if (i == N) {
                if (cnt < 1000) match[cnt] = m;
                cnt++;
                m = m + i - T[i];
                if (T[i] > 0) i = T[i];
                else i = 0;
            }
        } else {
            m = m + i - T[i];
            if (T[i] > 0) i = T[i];
            else i = 0;
        }
    }
    g << cnt << endl;
    for (int k = 0; k < 1000 && k < cnt; k++)
        g << match[k] << ' ';
    g << endl;

    return 0;
}