My solution is giving wrong answer on large input file . Please tell me what's wrong in my code?
#include "bits/stdc++.h"
using namespace std;
#define ll long long
ll pwr(ll a,ll b,ll mod) {a%=mod;if(a<0)a+=mod;ll ans=1; while(b) {if(b&1) ans=(ans*a)%mod; a=(a*a)%mod; b/=2; } return ans; }
ll modularInverse(ll a,ll m) {/*reminder: make sure m is prime*/ return pwr(a,m-2,m); }
const int MOD=1000000007;
int dp[301][301];
int recurse(string s, int st, int en, ll cumu[], ll pwr[], int hash2){
// case if u remove from here
if(st == en)return 1;
if(st > en)return MOD;
if(dp[st][en] != -1)return dp[st][en];
int ans = MOD+1;
ans = recurse(s, st+1, en, cumu, pwr, hash2) + 1 ;
// cout << en << " " << st << "\n";
for(int len = 2; len <= st; len++){
int end = st+len-1;
if(end >= s.length())break;
ll hash = (cumu[end] - cumu[st-1] + MOD)%MOD;
hash = (hash * modularInverse(pwr[st], MOD))%MOD;
if(hash == hash2){
ans = min(ans, recurse(s, st+len, en, cumu, pwr, hash2)+1);
continue;
}
for(int i = 0; i+len-1 < st; i++){
ll hash1;
if(i == 0){
hash1 = cumu[i+len-1]%MOD;
}
else{
hash1 = (cumu[i+len-1] - cumu[i-1] + MOD)%MOD;
hash1 = (hash1 * modularInverse(pwr[i], MOD))%MOD;
}
if(hash1 == hash){
// string conc = s.substr(st, len);
ans = min(ans, recurse(s, st+len, en, cumu, pwr, hash1)+2);
}
}
}
return dp[st][en] = ans;
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int t;
cin >> t;
int countt = 0;
while(t--){
countt++;
string s;
cin >> s;
for(int i = 0; i < 301; i++){
for(int j = 0; j < 301; j++)
// for(int k = 0; k < 301; k++)
dp[i][j]= -1;
}
ll cumu[s.length()];
ll pwr[s.length()];
memset(cumu, 0, sizeof cumu);
memset(pwr, 0, sizeof pwr);
for(int i = 0; i < s.length(); i++){
if(i == 0)pwr[i] = 1;
else {
pwr[i] = (pwr[i-1]*31)%MOD;
}
}
cumu[0] = 1*(s[0]-'a');
for(int i = 1; i < s.length(); i++){
cumu[i] = (cumu[i-1] + pwr[i]*(s[i]-'a'))%MOD;
}
string s1 = "";
int ans = recurse(s, 0, s.length()-1, cumu, pwr, 0);
// if(ans > 1)ans -= 1;
cout << "Case #" << countt << ": " << ans << "\n";
}
return 0;
}
