Cod sursa(job #2370644)

Utilizator catalintermureTermure Catalin catalintermure Data 6 martie 2019 12:56:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream inf("strmatch.in");
ofstream outf("strmatch.out");

int lps[2000000];
char s[2000005];
char pattern[2000005];
int result[1000];

void LPS(char *pat, int* lps) {
    int len = 0, i = 1;
    lps[0] = 0;
    int n = strlen(pat);
    while(i < n) {
        if(pat[len] == pat[i]) {
            lps[i] = ++len;
            i++;
        }
        else {
            if(len != 0) {
                len = lps[len - 1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int patsearch(char *pat, char *s) {
    LPS(pat, lps);
    int n = strlen(s);
    int m = strlen(pat);
    int i = 0, j = 0, rez = 0;
    while(i < n) {
        if(s[i] == pat[j]) {
            i++;
            j++;
        }
        else {
            if(j != 0) {
                j = lps[j - 1];
            }
            else {
                i++;
            }
        }
        if(j == m) {
            if(rez < 1000) {
                result[rez] = i - m;
            }
            rez++;
            j = lps[j - 1];
        }
    }
    return rez;
}


int main() {
    inf >> pattern >> s;
    int rez = patsearch(pattern, s);
    outf << rez << '\n';
    rez = min(rez, 1000);
    for(int i = 0; i < rez; i++) {
        outf << result[i] << ' ';
    }
    return 0;
}