[UVA] 10860 - Many a Little makes a Mickle

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10860 - Many a Little makes a Mickle
Source            : UVA Online Judge
Category          : String, DP
Algorithm         : Hashing, DP
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll          long long int  
#define ull         unsigned long long int  
  
static const int maxn = 1e4 + 5;  
static const int mod = 1e9 + 123;  
static const int inf = 1e8;  
  
int gen_base(const int before, const int after)  
{  
      auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();  
      mt19937 mt_rand(seed);  
//      mt19937 rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());  
      int base = uniform_int_distribution <int> (before+1, after) (mt_rand);  
      return base % 2 == 0 ? base - 1 : base;  
}  
  
int pow1[maxn];  
ull pow2[maxn];  
int base;  
  
void preCalc()  
{  
      assert(base < mod);  
      pow1[0] = 1;  
      pow2[0] = 1;  
      for (int i = 1; i < maxn; i++)  
      {  
            pow1[i] = (1LL * pow1[i-1] * base % mod);  
            pow2[i] = (pow2[i-1] * base);  
      }  
}  
  
struct Hash  
{  
      vector <ll> pref1;  
      vector <ull> pref2;  
      Hash() {}  
      Hash(const string &s) : pref1(s.size() + 1u, 0), pref2(s.size() + 1u, 0)  
      {  
            assert(base < mod);  
            int n = s.size();  
            for (int i = 0; i < n; i++)  
            {  
                  assert(base > s[i]);  
                  pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;  
                  pref2[i+1] = pref2[i] + s[i] * pow2[i];  
            }  
      }  
      // Polynomial hash of subsequence [pos, pos+len)  
      // If mxPow != 0, value automatically multiply on base in needed power.  
      // Finally base ^ mxPow  
      // 0 - Indexed  
      pair <ll, ull> getHash(const int pos, const int len, const int mxPow = 0)  
      {  
            ll hash1 = pref1[pos + len] - pref1[pos];  
            ull hash2 = pref2[pos + len] - pref2[pos];  
            if (hash1 < 0) hash1 += mod;  
            if (mxPow != 0)  
            {  
                  hash1 = 1LL * hash1 * pow1[mxPow - (pos + len - 1)] % mod;  
                  hash2 = hash2 * pow2[mxPow - (pos + len - 1)];  
            }  
            return make_pair(hash1, hash2);  
      }  
};  
  
#define pii         pair <int, ull>  
  
Hash hash_s;  
Hash hash_p[120];  
string s, p[120];  
int n, len, mxPow;  
  
int dp[maxn];  
bool memoize[maxn];  
  
int solve(int pos)  
{  
      if (pos >= len) return 0;  
      int &ret = dp[pos];  
      bool &mem = memoize[pos];  
      if (mem) return ret;  
      mem = 1;  
      int mini = inf;  
      for (int i = 0; i < n+n; i++)  
      {  
            int len_p = p[i].length();  
            if (pos + len_p > len) continue;  
            pii hsh_s = hash_s.getHash(pos, len_p, mxPow);  
            pii hsh_p = hash_p[i].getHash(0, len_p, mxPow);  
            bool same = (hsh_s == hsh_p);  
            if (same)  
            {  
                  int go = 1 + solve(pos+len_p);  
                  if (go < mini) mini = go;  
            }  
      }  
      return ret = mini;  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      base = gen_base(256, mod);  
      preCalc();  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            cin >> s;  
            len = s.size();  
            hash_s = Hash(s);  
            cin >> n;  
            mxPow = len;  
            for (int i = 0; i < n; i++)  
            {  
                  cin >> p[i];  
                  hash_p[i] = Hash(p[i]);  
                  mxPow = max(mxPow, (int)p[i].size());  
            }  
            for (int i = n; i < n+n; i++)  
            {  
                  p[i] = p[i-n];  
                  reverse(p[i].begin(), p[i].end());  
                  hash_p[i] = Hash(p[i]);  
            }  
            memset(memoize, 0, sizeof memoize);  
            int ans = solve(0);  
            cout << "Set " << tcase << ": ";  
            if (ans > len) cout << "Not possible.\n";  
            else cout << ans << ".\n";  
      }  
}