回文数 - 字符串数 [英] Palindrome count - string count
问题描述
给定一个字符串S，计算作为回文的非空子字符串的数量。
子字符串是字符串中任何连续的字符序列。
A如果字符串的反向与自身相同，则称字符串为回文。
如果它们出现在S中的不同位置，则两个子字符串不同
输入
输入只包含一行包含字符串S.
输出
打印单个数字，即字符串中的计数。
约束
1< = | S | < = 50
S只包含小写拉丁字母，即字符a到z。
我尝试了什么：
Given a string S, count the number of non empty sub strings that are palindromes.
A sub string is any continuous sequence of characters in the string.
A string is said to be palindrome, if the reverse of the string is same as itself.
Two sub strings are different if they occur at different positions in S
Input
Input contains only a single line that contains string S.
Output
Print a single number, the number of count in the string.
Constraints
1 <= |S| <= 50
S contains only lower case latin letters, that is characters a to z.
What I have tried:
#include <stdio.h>
#include<string.h>
int check(char s[],char a[],int x,int y)
{
int i,p=0;
for(i=x;i<=y;i++)
{
a[p]=s[i];
p++;
}
a[p]='\0';
int c=1;
int j=0;
while(j<=(strlen(a)/2))
{
if(a[j]!=a[strlen(a)-j-1])
{
c=0;
}
j++;
}
return c;
}
int main()
{
char s[50];
scanf("%s",s);
char a[50];
int i,j,c=0;
for(i=0;i<strlen(s);i++)
{
for(j=i;j<strlen(s);j++)
{
int b=check(s,a,i,j);
if(b==1)
{
c++;
}
}
}
printf("Number of palindromic substrings:%d",c);
return 0;
}
推荐答案
问题，它不计算所有字符串
problem,it's not counting all the strings
第一个操作是添加代码来跟踪代码的执行情况：
The first action is to add code to track what is doing your code:
...
while(j<=(strlen(a)/2))
{
if(a[j]!=a[strlen(a)-j-1])
{
c=0;
}
j++;
}
if (c==1)
{
printf("%s\n",a);
}
return c;
}
然后看看找到了哪些回文，哪些不是。
如果提示缺少的是足够的，去纠正。
否则，跳转到调试器，看看为什么它丢失了回文。
那里是一个工具，可以让您查看代码正在做什么，其名称是调试器。它也是一个很好的学习工具，因为它向你展示了现实，你可以看到哪种期望与现实相符。
当你不明白你的代码在做什么或为什么它做它做的时候，答案就是答案是调试器。
使用调试器查看代码正在执行的操作。只需设置断点并查看代码执行情况，调试器允许您逐行执行第1行并在执行时检查变量。
调试器 - 维基百科，免费的百科全书 [ ^ ]
掌握Visual Studio 2010中的调试 - 初学者指南 [ ^ ]
使用Visual Studio 2010进行基本调试 - YouTube [ ^ ]
调试器在这里向您展示您的代码正在做什么，您的任务是与什么进行比较应该这样做。
调试器中没有魔法，它没有找到错误，它只是帮助你。当代码没有达到预期的效果时，你就接近一个bug。
[更新]
顺便说一下，你的算法很幼稚，效率很低。工作量随着 s 的长度的平方而增长，它是O（n²）。
一个小小的分析显示任何大的回文都围绕着一个较小的一个，直到2或3号。所以，如果你在一个特定的中心附近没有一个小的回文，你就不会在同一个中心周围有一个较大的回文。
这意味着用'abcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh'你不需要检查大的回文，因为你没有小回报，这个优化是O（n）。
Then see which palindromes are found and which are not.
If the hint of the missing ones is enough, go to correct.
Otherwise, jump to debugger and see why it is missing a palindrome.
There is a tool that allow you to see what your code is doing, its name is debugger. It is also a great learning tool because it show you reality and you can see which expectation match reality.
When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.
[update]
By the way, your algorithm is very naive, and very inefficient. The workload grow with the square of length of s, it is O(n²).
A little analyze show that any large palindrome is built around a smaller one until size 2 or 3. So if you don't have a small palindrome around a given center, you will not have a larger one around same center.
This means that with 'abcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh' you don't need to check large palindromes because you don't have small ones, this optimization is O(n).
void palindromeSubStrs(string s)
{
map<string, int> m;
int n = s.size();
int R[2][n+1];
for (int j = 0; j <= 1; j++)
{
int rp = 0;
R[j][0] = 0;
int i = 1;
while (i <= n)
{
while (s[i - rp - 1] == s[i + j + rp])
rp++;
R[j][i] = rp;
int k = 1;
while ((R[j][i - k] != rp - k) && (k < rp))
{
R[j][i + k] = min(R[j][i - k],rp - k);
k++;
}
rp = max(rp - k,0);
i += k;
}
}
s = s.substr(1, n);
m[string(1, s[0])]=1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= 1; j++)
for (int rp = R[j][i]; rp > 0; rp--)
m[s.substr(i - rp - 1, 2 * rp + j)]=1;
m[string(1, s[i])]=1;
}
cout << "There are " << m.size()-1
<< " palindrome sub-strings";
map<string, int>::iterator ii;
for (ii = m.begin(); ii!=m.end(); ++ii)
cout << (*ii).first << endl;
}
int main()
{
palindromeSubStrs("abaabbbba");
return 0;
}
这篇关于回文数 - 字符串数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
