问题1019--分割字符串

1019: 分割字符串

时间限制: 1 Sec  内存限制: 128 MB
提交: 124  解决: 43
[提交] [状态] [讨论版] [命题人:]

题目描述

一个字符串X被称为Yanagram串,如果X是由Y的字符重新排序构成,不能移除或添加字符。比如”baba”, “abab”, “aabb””abba””aabb”anagram串, “aaab”,”aab””aabc”则不是。

一个字符串X被称为Y的子串,如果X是从Y串中移除一些字符(0个字符也可以),并且剩下字符的顺序不变。比如”ac”,”abd”,”abcd””abcd”的子串,”ca”,”abb”,”abcde”则不是。

那么,一个字符串X称为Yanagram子串,当且仅当存在一个字符串ZXZanagram串,ZY的子串。

对于一个长串S,罗老师想把他们分割成s1,s2,…,sn,也就是n个字符串,满足,当s1,s2,…,sn连接起来的时候刚好是S,同时,sisi+1anagram子串(0<i<n) 问题出来了,要满足这个条件,罗老师想知道,最多能分割成多少?

输入

输入一行字符串S

输出

输出最多分割成几份n

样例输入 Copy

ABABAB

样例输出 Copy

3

提示

【样例说明】

可以分成{AB},{AB},{AB}

 

【数据规模和约定】

字符串长度范围 [1, 500]

字符串只包含[‘A’- ‘Z’]

 

AAXAAAABX

4

 

ABCDEFGHIJKL

1

 

ABBABBBBXZ

2


O(n^3)的算法

状态: dp[i][j]表示以[I,j]作为最后一段且合法,这样可以分成多少段,

转移: dp[i][k]合法, str[k+1, j]包含str[i, k]的字符,那么,str[k+1, j]可以接到str[i, k]后面增加一段,于是 dp[k+1][j]=max(dp[k+1][j], dp[i][k]+1);

阶段: 以初始位置i为阶段

       For i=0 to n-1

         For k=i+1 to n-1

            For j=k+1 to n-1

判断包含: 使用数组le[26]表示[i, k]记录每个字母的数量, 使用数组ri[26]表示[k+1, j]每个字母的数量是否大于等于[i, k]的。

答案: 最后答案为max(dp[0~n-1][n-1])

来源/分类