[UVa] 11022 - String Factoring

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 11022 - String Factoring
Source            : UVa Live Archive
Category          : String, Dynamic Programing
Algorithm         : knuth morris pratt
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define vi           vector <int>
#define eb           emplace_back
#define sz(a)        a.size()
 
static const int maxn = 1e6 + 6;
 
string s;
 
vi LPS(const string &pat)
{
    vi lps; // Longest Prefix-Suffix
    lps.eb(0);
    int m = sz(s);
    int i = 1;
    int j = 0;
    while (i < m)
    {
        if (pat[i] == pat[j])
        {
            i++;
            j++;
            lps.eb(j);
        }
        else
        {
            if (j) j = lps[j-1];
            else i++, lps.eb(0);
        }
    }
    return lps;
}
 
int getMinimalLength(const string &s)
{
    int len = sz(s);
    vi lps = LPS(s);
    int minimalLength = len - lps[len-1];
    int times = len / minimalLength;
    int ans = -1;
    if (times * minimalLength == len) return minimalLength;
    return len;
}
 
int dp[85][85];
bool vis[85][85];
 
int solve(int i, int j) // returns minimum factoring cost of substring [i,j]
{
    if (i == j) return 1;
    int &ret = dp[i][j];
    bool &v = vis[i][j];
    if (v) return ret;
    v = 1;
    string ss = s.substr(i, j-i+1);
    int minLength = getMinimalLength(ss);
    if (minLength != j-i+1)
    {
        ret = solve(i, i+minLength-1);
    }
    else
    {
        int mini = 1234567;
        for (int k = i; k < j; k++)
        {
            int tcost = solve(i, k) + solve(k+1, j);
            if (tcost < mini) mini = tcost;
        }
        ret = mini;
    }
    return ret;
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
    while (cin >> s)
    {
        if (s[0] == '*') break;
        int len = sz(s);
        memset(vis, 0, sizeof vis);
        int ans = solve(0, len);
        cout << ans << endl;
    }
}