Cod sursa(job #2323917)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 19 ianuarie 2019 23:31:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
#define N 2000001
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int k[N],r[N];
int main(){
    int i,j=0,n=0;
    string a,b;
    in>>a>>b;
    for(i=1; i<a.length(); ++i){
        if(a[i]!=a[j])
            while(a[i]!=a[j] && j)
                j=k[j-1];
        if(a[i]==a[j])
            ++j;
        k[i]=j;
    }
    j=0;
    for(i=0; i<b.length(); ++i){
        if(b[i]!=a[j])
            while(b[i]!=a[j] && j)
                j=k[j-1];
        if(b[i]==a[j])
            ++j;
        if(j==a.length()){
            --j;
            while(b[i]!=a[j] && j)
                j=k[j];
            if(b[i]==a[j]) ++j;
			if(n<1000)
				r[++n]=i-a.length()+1;
        }
    }
    out<<n<<"\n";
    for(i=1; i<=min(n,1000); ++i)
        out<<r[i]<<" ";
    return 0;
}