首页 > 代码库 > UVA 12718 Dromicpalin Substrings(寻找字符串连续子串的回文)

UVA 12718 Dromicpalin Substrings(寻找字符串连续子串的回文)

转载请注明出处:http://blog.csdn.net/u012860063


题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4456


题意:寻找给出字符串的字串中是回文的个数(注意:字串中字母换位置后能组成回文也要算在内,例如:aab之类的可以换位置为:aba 也是一个回文)。


思路:只需统计每个字母出现的次数,再统计出现次数中为奇数的个数,如果某个字串中出现奇数次数的字母有一个或者没有,那么就符合题目要求!


代码如下:

#include <cstdio>
#include <cstring>
int main()
{
	int t, cont, i, j;
	char s[1047];
	int c[47];
	int cas =0;
	while(~scanf("%d",&t))
	{
		getchar();
		while(t--)
		{
			gets(s);
			int len = strlen(s);
			int k = len;
			for(i = 0; i < len; i++)
			{
				cont = 1;
				memset(c,0,sizeof(c));
				c[s[i]-'a']++;
				for(j = i+1; j < len; j++)
				{
					c[s[j]-'a']++;
					if((c[s[j]-'a'])%2 == 1)
						cont++;
					else
						cont--;
					if(cont == 1 || cont == 0)//出现奇数次数的字母有一个或者没有
						k++;
				}
			}
			printf("Case %d: %d\n",++cas,k);
		}
	}
	return 0;
}