Cod sursa(job #1791899)

Utilizator DenisacheDenis Ehorovici Denisache Data 29 octombrie 2016 20:18:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define NMAX 2000005

char pattern[NMAX], text[NMAX];
int pTable[NMAX];

void searchPattern(char *pattern, char *text) {
    int len = 0, i = 0, n = strlen(pattern) - 1, m = strlen(text) - 1;
    vector <int> sol;

    while (i <= m) {
        if (text[i] == pattern[len]) {
            len++;
            i++;
        }

        if (len == n + 1) {
            if (sol.size() < 1000) sol.push_back(i - len);
            len = pTable[len - 1];
        }
        else if (i <= m && text[i] != pattern[len]) {
            if (len != 0) {
                len = pTable[len - 1];
            }
            else i++;
        }
    }

    printf("%d\n", sol.size());
    vector <int> ::iterator it;
    for (it = sol.begin(); it != sol.end(); it++) {
        printf("%d ", *it);
    }
}

void buildPartialTable(char *s) {
    int len = 0, i = 1, n = strlen(s);
    pTable[0] = 0;

    while (i < n) {
        if (s[i] == s[len]) {
            len++;
            pTable[i] = len;
            i++;
        }
        else if (len != 0) {
            len = pTable[len - 1];
        }
        else i++;
    }
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    gets(pattern);
    gets(text);

    buildPartialTable( pattern );
    searchPattern( pattern, text);
}