Cod sursa(job #1983341)

Utilizator lraduRadu Lucut lradu Data 21 mai 2017 18:31:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <string>

#define pb push_back
#define mp make_pair
#define mod 1000000007
#define PI 3.141592653589793;

using namespace std;

int lps[4000005];
int result[1002];

int main() {
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    string a, b;
    f>>a>>b;

    int ind = 0, i = 1, j = 0, n = a.size(), m = b.size(), nr = 0;
    while(i < n){
        if(a[i] == a[ind]){
            lps[i] = ind + 1;
            i++;
            ind++;
        } else if(ind){
            ind = lps[ind - 1];
        } else {
            i++;
        }
    }

    i = 0;
    while(i < m){
        if(b[i] == a[j]) {
            i++;
            j++;
        } else if(j){
            j = lps[j - 1];
        } else {
            i++;
        }

        if(j == a.size()){
            nr++;
            j = lps[j-1];
            if(nr <= 1000)
                result[nr] = i - n;
        }
    }

    g<<nr<<'\n';
    for(int i=1; i <= min(nr, 1000); i++)
        g<<result[i]<<' ';
}