Cod sursa(job #2244476)

Utilizator axelteoTeodor Dutu axelteo Data 22 septembrie 2018 20:16:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <string>

using namespace std;

#define MAX_STR 2000000
#define MAX_FINDS 1000

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

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

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]) {
            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 && numApp < MAX_FINDS; ++i) {
        while (j && pattern[j] != str[i]) {
            j = map[j - 1];
        }

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

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

    fout << numApp << '\n';

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

    return 0;
}