EOJ 3194 字符串消除

给定一个由大写字母’A’、’B’、’C’构成的字符串s，按如下进行消除过程：

1、字符串s中连续相同字母组成的子串，如果子串的长度大于1，那么这些子串会被同时消除，余下的字符拼成新的字符串。

例如：”ABCCBCCCAA”中”CC”,”CCC”和”AA”会被同时消除，余下”AB”和”B”拼成新的字符串”ABB”。

2、反复进行上述消除，直到新的字符串中相邻字符都不相同为止。

例如：”ABCCBCCCAA”经过一轮消除得到”ABB”，再经过一轮消除得到”A”。

假设在对字符串s消除开始前，允许在s中任意位置(第一个字符之前、最后一个字符之后以及相邻两个字符之间)插入任意一个字符(‘A’,’B’或者’C’)，得到字符串t，然后对字符串t经过一系列消除。

请问该如何插入字符，使得字符串t中被消除掉的字符总数（包括插入的字符）最多？

Input

第 1 行：整数 T (1≤T≤10) 为问题数。

第 2 ~ T+1 行：每个问题占一行，每行输入一个由’A’、’B’、’C’组成的字符串s，长度不超过100。

Output

对每个测试数据，首先输出一行问题的编号（0 开始编号，格式：case #0: 等）。在接下来一行中输出被消除掉的最大字符数。

Examples

Input

3

ABCBCCCAA

AAA

ABC

Output

case #0:

9

case #1:

4

case #2:

2

Note

第一组数据：在”ABCBCCCAA”的第2个字符后插入’C’得到”ABCCBCCCAA”，消除后得到”A”，总共消除9个字符(包括插入的’C’)。

 #include <iostream>

 #include <string>

 using namespace std;

 string x[] = { "A","B","C" };

 void del(int& ans,string tmp)

 {

     int len=tmp.size();

     while()

     {

         int flag=;//判断是否可以继续消除

         for(string::iterator it=tmp.begin(),t,s;it<tmp.end()-;)//小心it越界

             if(*(it+)==*it)

             {

                 flag=;

                 int x=it-tmp.begin();//x记录上次消除位置，以便从后继续消除

                 t=it;

                 while(it<tmp.end()-&&*(it+)==*it) it++;

                 tmp.erase(t,it+);

                 x=x<?:x;

                 it=tmp.begin()+x;

             }

             else it++;

         if(flag==) break;

     }

     ans=ans>(len-tmp.size())?ans:len-tmp.size();

 }

 int main()

 {

     int T;cin>>T;

     for(int m=;m<T;m++)

     {

         string s;cin>>s;

         int ans=;

         for(int i=;i<=s.size();i++)

         {

             for(int j=;j<;j++)

             {

                 string tmp=s;tmp.insert(i,x[j]);

                 del(ans,tmp);

             }

         }

         printf("case #%d:\n%d\n",m,ans);

     }

     return ;

 }

在字符串的每个空格(包括首尾)处插入A或B或C，消除连续相同字母组成的字串，判断无可消除字串后退出，经过几次比较，得出消除最多的字符个数。

注意是同时消除，因此应该在消除之后从消除的地方继续向后找字串，而不是从头开始找。

如ABCCBCCCAA，第一次消除CC，CCC，AA，而不是第一次消除得ABBCCCAA，然后继续消除BB，CCC，AAA，这样结果就是全部消除了，这也是我一开始WA的原因。

巴特西

EOJ 3194 字符串消除

Input

Output

Examples

Note

最新文章

热门文章