问题描述
- c语言题目求解答~~~~~
- 自然数列1，2，3，4，5，......大家都很熟悉，现将自然数列写成一排，数字中间不留空格等任何分隔符号就成了如下这样
123456789101112131415161718192021......
这是一个很长很长的串，现要求在这个串中找到一个最先出现给定子串的位置。例如给定子串1112，这该子串最先出现在串中第12个字符位置
为了能简化处理，我们保证评判时给定的子串在串中一定出现，且位置不大于10000.输入格式
给定的子串（一行由数字字符构成的字符串，不超过80个字符），请使用scanf(""%s""........)读取
输出格式最先出现子串的位置
输入样例1112
输出样例12
解决方案
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
解决方案二：
假定是子串是四个字符，从输入结果第一个开始，每次读取四个字符，与之比较
解决方案三：
#include
int main()
{
char s[80];
int l a[10000] i k = 9 b[10000] j o c[10000] f = 0 q x;
scanf(""%s"" s);
for(i = 0 q = 0; s[i] != ''; i++ q++)
{
c[i] = s[i] - '0';
// printf(""%d"" c[i]);
}
// printf(""%d"" q);
for(i = 0; i < 10000; i++)
{
l = i+1;
if(l > 9)
{
j = 0;
while(l)
{
b[j++] = l % 10;
l /= 10;
}
x = j - 1;
for(j = x; j >= 0; j--)
{
a[k++] = b[j];
// printf(""%d"" a[k-1]);
}
}
else
{
a[i] = l;
// printf(""%d"" a[i]);
}
j = 0;
for(o = 0; a[o] != ''; o++)
{
if(a[o] == c[j])
{
f++;
j++;
if(c[j] == '')
break;
}
else if(a[o] == c[0])
{
f = 1;
j = 1;
}
else
{
f = 0;
j = 0;
}
}
if(f == q)
{
printf(""%d"" i+1);
break;
}
f = 0;
}
return 0;
}
这是我自己的写的代码，不知道哪里错了，求大神解答
解决方案四：
#include
int main()
{
char s[80];//要找的子串
int l a[10000] i k = 9 b[10000] j o c[10000] f = 0 q x;
scanf(""%s"" s);
for(i = 0 q = 0; s[i] != ''; i++ q++)//q为子串个数
{
c[i] = s[i] - '0';//将char型数组转换为整型数组存放
}
for(i = 0; i < 10000; i++)
{
l = i+1;//从1开始到10000存进数组a中以便比较
if(l > 9)
{
j = 0;
while(l)
{
b[j++] = l % 10;
l /= 10;
}
x = j - 1;
for(j = x; j >= 0; j--)
{
a[k++] = b[j];//i>=10开始存放在b数组中，再逆序存放在a数组中，k是从9开始的
}
}
else
{
a[i] = l;//小于10的直接存放在a数组中
}
j = 0;
for(o = 0; a[o] != ''; o++)//将当前a数组与给定子串一一比较
{
if(a[o] == c[j])
{
f++;//若有相同的数组f自增，f是记录共有多少个数字相同了
j++;//比较完当前的再比较下一个
if(c[j] == '')
break;
}
else if(a[o] == c[0])//如果不同，则看下跟第一个数字相同不，相同就从第二个数字开始比了
{
f = 1;
j = 1;
}
else
{
f = 0;//不同f清零
j = 0;
}
}
if(f == q)//如果连续相同的个数f和给定子串长度q相同输出当前位置i+1
{
printf(""%d"" i+1);
break;
}
f = 0;
}
return 0;
}
解决方案五：
给你一个思路吧，自己去设计代码。
首先，这个题的原型是：
12345678910111213....这个字符串
给你一个整数N，比如1000，求这个数在这个字符串中的位置。
这样子，你是不是基本上有思路了？
注意：
1位数 9个
2位数 90个
3位数 900个
4位数 9000个
...
其次，看这个题，是不是可以转化成上述的问题呢？
答案肯定是可以的。
首先位置不大于10000，说明最大也就4位数。
只要知道所给字符串的第一个数字是多少就行了。
从1位到4位，首先判断成功的，即最先出现。
注意，所给字符串的第一个数字可能已经被分割了。
被分割的情况，就是分别往后跳1-3个字符，再按正常情况判定。
最后算出结果的时候，再将结果位置往前跳回去。
解决方案六：
KMP看毛片算法。。。
解决方案七：
#include
#include
int main()
{
char s[80];
int a[80] b[100000] d[10] k = 0 t i j = 0 l q f = 0 p;
scanf(""%s"" &s);
p = strlen(s);
for(i = 0; i < p; i++)
a[i] = s[i] - '0';
for(i = 0; i < 10000; i++)
{
l = i+1;
k = 0;
if(l > 9)
{
while(l)
{
d[k++] = l % 10;
l /= 10;
}
k = k-1;
for(; k >= 0; j++ k--)
b[j] = d[k];
}
else
b[j++] = l;
q = 0;
f = 0;
for(t = 0; t < j; t++)
{
if(b[t] == a[q])
{
q++;
f++;
}
else if(b[t] == a[0])
{
f = 1;
q = 1;
}
else
{
q = 0;
f = 0;
}
if(q == p)
break;
}
if(f == p)
{
printf(""%d"" i+1);
break;
}
}
return 0;
}
我自己改进了下，自己测试数据是对的，虽然没通过。。郁闷