Cod sursa(job #1716588)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 13 iunie 2016 09:49:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

#define DMAX 2000002
using namespace std;

vector<int> Sol, T;
char W[DMAX], S[DMAX];
int sizeW, sizeS;

void Read();
void KMP();
void Compute_Prefix();
void Write();

int main()
{
    Read();
    KMP();
    Write();

    return 0;
}

void Compute_Prefix() {
    T.assign(sizeW, 0);
    T[0] = -1;
    int pos = 2, cnd = 0;
    while(pos <= sizeW) {
        if(W[pos - 1] == W[cnd]) {
            T[pos++] = cnd + 1;
            cnd ++;
        }
        else if(cnd > 0)
            cnd = T[cnd];
        else
            T[pos++] = 0;
    }
}

void KMP() {
    Compute_Prefix();
    int m = 0, i = 0;
    while(m + i < sizeS) {
        if(W[i] == S[m + i]) {
            if(i == sizeW - 1)
                Sol.push_back(m);
            i++;
        }
        else if(T[i] > -1) {
            m = m + i - T[i];
            i = T[i];
        }
        else {
            m = m + i + 1;
            i = 0;
        }
    }
}

void Read() {
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);
    //cin >> W >> S;
    scanf("%s%s", W, S);
    sizeW = strlen(W);
    sizeS = strlen(S);
}

void Write() {
    cout << Sol.size() << '\n';
    for(int i = 0; i < Sol.size() && i < 1000; ++i)
        cout << Sol[i] << ' ';
    cout << '\n';
}