Submission #857195

---

Source Code Expand

#include <cmath>
#include <vector>
#include <iostream>
#include <limits>
#include <iostream>
#include <vector>
#include <cassert>
#include <complex>
#include <cstring>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long Long;

int mat[4010][4010];
void comp(string &S, int s){
	int i = 0, j = -1;
	vector<int> T(S.size()+1);
	T[0] = -1;
	while(i+s < S.size()){
		while(j >= 0 && S[i+s] != S[j+s]){
			j = T[j];
		}
		i++;j++;
		T[i] = j;
		int ss = i;
		int p = ss - j;
		if(p > 0 && p != ss && ss % p == 0){
			mat[s][s+i-1] = p;
		}else{
			mat[s][s+i-1] = -1;
		}
	}
}
int mem[4010];
int cat[4010];
int dp(int i){
	if(i < 0)return 0;
	int w = 1000000;
	if(mem[i] != -1)return mem[i];
	int c = 0;
	for(int j = 0; j < i; ++j){
		if(mat[j][i] == -1){
			int t = dp(j-1) + 1;
			if(t < w){
				w = t;
				c = 1;
			}else if(t == w){
				c++;
			}
		}
	}
	cat[i] = c;
	return mem[i] = w;
}

int main(){
	
	string S;
	cin >> S;
	for(int i = 0; i < S.size(); ++i){
		comp(S,i);
	}
	memset(mem,-1,sizeof(mem));
	cout << dp(S.size()-1) << endl;
	cout << cat[S.size()-1] << endl;
	
}


/*


 */

Submission Info

Judge Result