Cod sursa(job #2485652)

Utilizator bogdanc2002Bogdan Colta bogdanc2002 Data 1 noiembrie 2019 21:02:34
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include<bits/stdc++.h>
#define d 256
using namespace std;
ifstream fin("strmatch.in");ofstream fout("strmatch.out");
int main(){
    string A,B;
getline(fin,B);getline(fin,A);
int n=A.length();int m=B.length();
int h=1,t=0,p=0;int q=7;int w=0;int arr[100];
int i,j;
for(i=0;i<m-1;i++){
    h=(h*d)%q;
}
for(i=0;i<m;i++){
    p=(p*d+B[i])%q;
    t=(t*d+A[i])%q;
}
for(i=0;i<=n-m;i++){
    if(t==p){
        for(j=0;j<m;j++){
            if(B[j]!=A[i+j])break;
        }
        if(j==m){arr[w]=i;w++;}
    }
    if(i<n-m){
        t=(d*(t-A[i]*h)+A[i+m])%q;
        if(t<0)t+=q;
    }
}
fout<<w<<endl;
for(i=0;i<w;i++)fout<<arr[i]<<' ';
return 0;}