Cod sursa(job #2244439)

Utilizator axelteoTeodor Dutu axelteo Data 22 septembrie 2018 19:21:56
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 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 + 1;
            ++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) {
        if (str[i] == pattern[j]) {
            if (j == pattLen - 1) {
                apps[++numApp] = i - pattLen + 1;
                j = map[j];
            } else {
                ++j;
            }
        } else {
            j = map[j];
        }
    }

    fout << numApp << '\n';

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

    return 0;
}