panther
posts - 43,comments - 3,trackbacks - 0
ZZ 统计字符串中所有子串是对称串的个数
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2744

比如：输入字符串aba，其一维子串a，b，a都是对称串，它本身也是对称的，所以其输出为4。
不难看出所有对称串可以分为3类：
I)单个字符组成的对称串，比如a，b，c
II)偶数长度的对称串，比如aa，abba
III)奇数长度的对称串，即：除中间位置的字符可以出现奇数次，两边的字符必须成对出现，比如aca，abcba

其实情况I)是情况III)的特殊形式，由于我们可以直接获得输入串的长度，故把情况I)单独拿出来就不必计算了
 1#include "stdio.h"
 2#include "stdlib.h"
 3#include "string.h"
 4#include "iostream"
 5
 6using namespace std;
 7#if 0
 8typedef unsigned __int64 uint64;
 9#else 
10typedef unsigned long long uint64;
11
12#endif
13char buf[5001];
14
15uint64 cnt()
16{
17    uint64 ret = 0;
18    size_t len = strlen(buf);
19    ret += len;
20
21    for (int i = 0; i <len-1; ++i)
22    {
23        int j = i + 1;
24        int k = i;
25        while (k >=0 && j <= len-1 && buf[k] == buf[j])
26        {
27            ++ret;
28            --k,++j;
29        }
30    }
31
32    for (int i = 1; i <len-1; ++i)
33    {
34        int j = i + 1, 
35            k = i - 1;
36        while (k >=0 && j <= len-1 && buf[k] == buf[j])
37        {
38            ++ret;
39            --k,++j;
40        }
41    }
42    return ret;
43}
44
45int main()
46{
47
48    while (cin >> buf)
49    {
50        cout << cnt() << endl;
51    }
52    return 0;
53}
posted on 2010-05-10 11:02 RUI 阅读(574) 评论(0)  编辑 收藏 引用 所属分类: algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


Copyright ©2024 RUI Powered By博客园 模板提供：沪江博客