제가 JMBOOK으로 공부를하고 있는 학생입니다.

이책에서 나온 풀이 방식대로 카라츠바 알고리즘을 이용하여 문제를 풀었는데 시간 초과가 나옵니다.

언어는 c++이고요.
소스는 아래 있고요 왜 시간초과가 나오는지 이유를 알려주시면 감사하겠습니다

~~~c++

#include
#include
#include
#include
#include
using namespace std;
vector mutiply(const vector& a,const vector& b)
{
vectorc(a.size()+b.size()+1,0);
for(int i=0;i {
for(int j=0;j {
c[i+j]+=a[i]*b[j];
}
}
return c;
}
void addto(vector& a,vector& b, int k)
{
a.resize(max(a.size(), b.size()+k));
for(int i = 0; i < b.size(); i++)
{
a[i+k]+=b[i];

}

}
void subfrom(vector& a,vector&b)
{
a.resize(max(a.size(), b.size()+1));
for(int i = 0; i < b.size(); i++)
{
a[i]-=b[i];
}
}
vector karastuba(vector a,vector b)
{
int an = a.size(),bn = b.size();
if(an < bn)karastuba(b,a);
if(an == 0||bn == 0)return vector();
if(an <= 50) return mutiply(a,b);
int half=an/2;
vector a1(a.begin(),a.begin() + half);
if(bn > half)bn=half;
vector b1(b.begin(),b.begin()+ bn);
vector a0(a.begin() + half,a.end());
vector b0(b.begin() + bn , b.end());
vector z2 = karastuba(a1 , b1);
vector z0 = karastuba(a0, b0);
addto(a0,a1,0);
addto(b0,b1,0);
vector z1 = karastuba(a0,b0);
subfrom(z1,z0);
subfrom(z1,z2);
vector ret;
addto(ret,z2,half+half);
addto(ret,z1,half);
addto(ret,z0,0);
return ret;
}
int hugs(vector& a,int n,int m)
{
int hug=0;
for(int i = n-1; i < m; i++)
{
if(a[i]==0)hug++;
}
return hug;
}
void input()
{
string member,fans;
int n,m;
getline(cin,member);
getline(cin,fans);
n=member.size(),m=fans.size();
vector a(n),b(m);
for(int i = 0; i < n;i++) a[i]=(member[i]=='M');
for(int i = 0; i < m;i++) b[m-i-1]=(fans[i]=='M');
vector c = karastuba(a,b);
printf("%d\n",hugs(c,n,m));
}
int main()
{
int T;
scanf("%d\n",&T);
while(T--)
{
input();
}
return 0;
}

</spoiler>