首页 > 代码库 > 超长字符串
超长字符串
一、问题描述
给定一个字符串S:123456789101112131415161718192021...它是由所有自然数从小到大依次排列起来的。任意给一个数字串S1，绒衣知道它一定在S中出现多次。编程出它第一次出现的位置。例如对于串“81”，它最先出现的位置为27。
二、算法描述
分四种情况：
（1）字串是连续的若干个数组成的，如12131415 是由12,13,14,15的连续数字组成的，搜索的最小数字位置为n=12的第一位，偏移为0
（2）字串的前后有一部分子串相同，如1234567123 ，前三个数和后三个数都是123。则n=1234567是要搜索的最小数字，偏移为0
（3）字串的前后有一部分子串，后一个比前一个多1，如123454124。前三个数是123，后三个数是124，则最小搜索数字是n=454124(去掉最开始的三个数)，偏移为-3
（4）没有出现上述三种情况，如1123129，则最小的搜索数为n=9112312，偏移为1。
上诉的偏移是指搜索到数字n首位出现的位置在加上偏移，就等于最终要求得的结果。
三、代码实现
#include<iostream>#include<string>using namespace std;//将字符串翻译成数字int str2int(string str){ int t=0; for(int i=0;i<str.size();i++){ t=t*10+(str[i]-‘0‘); } return t;}int check9s(string str){ for(int i=0;i<str.size();i++){ if(str[i]!=‘9‘){ return 0; } } return 1;}//首先考虑数字是否是m位连续的数字组成如（111213，最先出现的位置11， 12， 13串位置）int continueStrSearch(string str){ for(int i=1;i<=str.size()/2;i++){ int startNum=0; int curNum=0; int preNum=0; int cursor=0; int span=i; int flag=1; while(cursor<str.size()){ preNum=curNum; string subs=str.substr(cursor,span); //cout<<"subs="<<subs<<endl; curNum=str2int(subs); if(cursor==0){ startNum=curNum; }else if(preNum+1!=curNum){ flag=0; break; } cursor+=span; if(check9s(subs)){ span++; } //cout<<span<<endl; } if(flag==1){ return startNum; } } return -1;}struct reS{ int minNum; int off;};//找到最小的数和偏移reS findP(string str){ reS res; int minNum=0; int flag=0; int m=0; int n=str.size(); //找到一个数前m位和后m位相等或后比前大1的最大位置 如 1234123 返回3 13814 返回2 121212 返回1 for(int i=1;i<str.size()/2;i++){ int f=1; for(int j=0;j<i;j++){ if(str[j]!=str[n-i-1+j]){ f=0; } } if(f==1){ m=i; if(str[i]==str[n-1]){ flag=1; }else if(str[i]+1==str[n-1]){ flag=2; } } } string s; //找到最小的数 if(flag==0){ s.push_back(str.back()); s=s+str.substr(0,str.size()-1); res.off=1; }else if(flag==1){ s=str.substr(0,str.size()-(m+1)); res.off=0; }else if(flag==2){ s=str.substr(m+1,str.size()-(m+1)); res.off=-(m+1); } minNum=str2int(s); res.minNum=minNum; return res; }int minPos(reS res){ int t=10; //cout<<res.minNum<<" "<<res.off<<endl; int num=res.minNum-1; int posNum=num+1; int off=res.off; while(num/t){ posNum+=(num-t+1); t=t*10; } posNum=posNum+off; return posNum;}//计算这个字串的范围（即可能出现在两个数字之间）int main(){ while(1){ cout<<"输入数字字符串："<<endl; string numStr; cin>>numStr; reS res; int startNum; int t=continueStrSearch(numStr); if(t!=-1){ startNum=t; res.minNum=t; res.off=0; }else{ res=findP(numStr); startNum=res.minNum; } int minpos=minPos(res); cout<<"minNum="<<res.minNum<<" off="<<res.off<< " minPos="<<minpos<<endl; } system("pause"); return 0;}
四、运行结果
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。