Cod sursa(job #2244489)

Utilizator axelteoTeodor Dutu axelteo Data 22 septembrie 2018 20:29:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <string>

using namespace std;

#define MAX_STR 2000000
#define MAX_FINDS 1001

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

string pattern, str;
int numApp, map[MAX_STR], apps[MAX_FINDS];

void buildSufPref() {
    int i, j, len = (int)pattern.size();

    for (i = 1, j = 0; i < len; ++i) {
        while (pattern[i] != pattern[j] && j) {
            j = map[j - 1];
        }

        if (pattern[i] == pattern[j]) {
            ++j;
        }

        map[i] = j;
    }
}

int main() {
    fin >> pattern >> str;

    int strLen = (int)str.size();
    int pattLen = (int)pattern.size();

    if (pattLen > strLen) {
        fout << 0 << '\n';
        return 0;
    }

    buildSufPref();

    for (int i = 0, j = 0; i < strLen; ++i) {
        while (j && pattern[j] != str[i]) {
            j = map[j - 1];
        }

        if (str[i] == pattern[j]) {
            ++j;
        }

        if (j == pattLen) {
            if (++numApp < MAX_FINDS) {
                apps[numApp] = i - pattLen + 1;
            }

            j = map[j - 1];
        }
    }

    fout << numApp << '\n';

    numApp = (numApp > 1000 ? 1000 : numApp);

    for (int i = 1; i <= numApp ; ++i) {
        fout << apps[i] << ' ';
    }
    fout << '\n';

    return 0;
}