字符串搜索问题( 求算法或者描述）

给一个字符串S: "01234567891011121314151617181920212223…… " ，它是由所有自然数由小到大依次排列起来的。任意给一个字符串S1，容易知道它在字符串S中出现无穷多次。编程求出他第一次出现的位置。

比如：串"18”最先出现的位置是 26，串"34"最先出现的位置是3

用什么编~~c，c#，java，vb...？？？

如果是指要通用任意字符串模式匹配算法，而且原字符串(长m)和模式字符串(长n)均已知，请参考kmp算法，可以在O(m + n)内解决问题。

如果是指要这个题的一个算法，对于无限长的S，我有这样的一个算法，时间复杂度最差约为 O(n^3)，n为任意给出的串的长度 把任意给出的字符串叫做s1，根据题意，可以知道s1一定是某个k位数m和它相邻的数字产生的一个串（一定有多种可能的数字m），而且它第一次出现的位置一定是其中最小的m所产生的。 由此，我们可以得到如下算法： for(k = 1; k <= n; k++){ //枚举位数 for(m = s1中的第一个k位数; m的位置没有越过s1; m = 下一个k位数){ //枚举s1中所有可能的k位数，对应每个k值有n - k + 1种可能 if(m是合法的k位数){ s2 = 根据s1中m的位置和值产生的一个和s1相同长度的串 if(s1 == s2){ 成功匹配，得到m } } } } 之后，又知道1位数有10个，2位数有90，3位数有900个，4位数有9000个。。。。。我们就可以根据求得的k的值和m的值和位置在O(n)内求得结果。

又枚举k最多有n个，枚举可能的k位数最多有n - k + 1个，在m合法的情况下产生s2和判断s1==s2需要O(n)，可得总的时间复杂度O(n^3)

程序代码如下：

#include <iostream.h> int length(char *s) { int i; for(i=0;s[i]!='\0';i++); return i; } int StringSearch(char *str,char *substr) { int i,j; int lenstr=length(str); int lensubstr=length(substr); for(i=0;i<lenstr-lensubstr;i++) { for(j=0;j<lensubstr&&str[i+j]==substr[j];j++); if(substr[j]=='\0')return i+j-lensubstr;

} return -1; } void main() { char s1[100]; char s2[100]; cout<<"string:";cin>>s1; cout<<"substring:";cin>>s2; int p= StringSearch(s1,s2);//找到的位置存到p变量中，若p=-1则表示没找到

if(p==-1)cout<<"没找到！"<<endl;

else { cout<<"注：起始位置是0."<<endl; cout<<"找到了，位置："<<p<<endl; } }

程序运行结果：

string s = "012345678910

建议你查阅一下kmp算法 算法是通用的 和语言无关