Cod sursa(job #1974736)

Utilizator GeorginskyGeorge Georginsky Data 28 aprilie 2017 17:15:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
const int N=2e6+5;
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n, pr[N], pz[1005];
string a, b;
int main(){
    getline(in, a);
    getline(in, b);
    a.insert(a.begin(), ' ');
    b.insert(b.begin(), ' ');
    int j=0;
    for(int i=2; i<a.size(); i++){
        while(j&&a[j+1]!=a[i])j=pr[j];
        if(a[j+1]==a[i])j++;
        pr[i]=j;
    }
    j=0;
    for(int i=1; i<b.size(); i++){
        while(j&&a[j+1]!=b[i])j=pr[j];
        if(a[j+1]==b[i])j++;
        if(j==a.size()-1){
            j=pr[a.size()-1], n++;
            if(n<=1000)pz[n]=i-(a.size()-1);
        }
    }
    out<<n<<"\n";
    for(int i=1; i<=min(n,1000); i++)out<<pz[i]<<" ";
    return 0;
}