백준 1786 찾기 (C++)

문자열 탐색 알고리즘을 사용하라는 문제입니다. kmp나 라빈 카프 둘 중 아무거나 사용하면 됩니다. 보이어무어 알고리즘 같은경우 최악의 경우 (N*M)이므로 시간복잡도를 넘게됩니다. 저는 라빈카프를 사용해서 풀었습니다. 영어소문자와 띄어쓰기로 이루어져있으므로 사용되는 문자가 61개정도되는데 충분히 큰 radix와 mod를 사용하셔야 합니다. 

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
long long MOD=1000000007;
long long mod(long long x)
{
	if(x>=0) return x%MOD;
	else return ((-x/MOD+1)*MOD+x)%MOD;
}
vector<int> ans;
int main(){
    fast_io();
    string a,b;
    getline(cin,a);
    getline(cin,b);
    long long bkr=0;
    long long akr=0;
    long long temp=1;
    if(a.size()<b.size()){
        cout<<"0\n";
        return 0;
    }
    int al=(int)a.size();
    int bl=(int)b.size();
    for(int x=bl-1;x>=0;x--){
        akr=mod(akr+(temp)*(long long)a[x]);
        bkr=mod(bkr+(temp)*(long long)b[x]);
        if(x!=0) temp=mod(temp*9973LL);
    }
    if(akr==bkr) ans.push_back(1);
    for(int x=1;x<=al-bl;x++){
        akr=mod(mod(9973LL*mod(akr-a[x-1]*temp))+a[x+bl-1]);
        if(akr==bkr) ans.push_back(x+1);
    }
    cout<<ans.size()<<'\n';
    for(auto i : ans){
        cout<<i<<" ";
    }
}