> // MyFirstApp.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
> //
> 
> #include <iostream>
> #include <vector>
> #include <stdio.h>
> #include <math.h>
> #include <algorithm>
> 
> using namespace std;
> 
> typedef __int64 lld;
> 
> const int MAXN = 20010;
> 
> struct BigNum
> {
> 	int dig[512];//题目说最多200位，平方之后最多400位
> 	int len;
> 	BigNum() {}
> 	BigNum(int arr[], int size) 
> 	{
> 		clr();
> 		len = size;
> 		for (int i = 0; i < len; i++)
> 		{
> 			dig[len - i - 1] = arr[i];
> 		}
> 	}
> 	void clr()
> 	{
> 		memset(dig, 0, sizeof(int) * 512);
> 		len = 1;
> 	}
> 
> 	void operator --()
> 	{
> 		dig[0]--;
> 		int bit=0;
> 		while (dig[bit] < 0)
> 		{
> 			dig[bit] += 10;
> 			dig[bit + 1] --;
> 			bit++;
> 		}
> 
> 		while (len > 1 && dig[len - 1] == 0)
> 		{
> 			len--;
> 		}
> 	}
> 
> 	int Compare(const BigNum& other) const
> 	{
> 		if (len < other.len)
> 		{
> 			return -1;
> 		}
> 
> 		if (len>other.len)
> 		{
> 			return 1;
> 		}
> 
> 		for (int i = len-1; i>=0; i--)
> 		{
> 			if (dig[i] != other.dig[i])
> 			{
> 				return dig[i] - other.dig[i];
> 			}
> 		}
> 
> 		return 0;
> 	}
> 
> 	void operator ++()
> 	{
> 		dig[0]++;
> 		int bit = 0;
> 		while (dig[bit] > 9)
> 		{
> 			dig[bit] -= 10;
> 			dig[bit + 1] ++;
> 			bit++;
> 		}
> 
> 		if (dig[len])
> 		{
> 			len++;
> 		}
> 	}
> 
> 	void Add(int x)
> 	{
> 		dig[0]+=x;
> 		for(int i=0;i<len;i++)
> 		{
> 			if(dig[i]>=10)
> 			{
> 				dig[i+1]+=dig[i]/10;
> 				dig[i]%=10;
> 			}
> 		}
> 
> 		while(dig[len])
> 		{
> 			dig[len+1]+=dig[len]/10;
> 			dig[len]%=10;
> 			len++;
> 		}
> 	}
> 
> 	void print()
> 	{
> 		for(int i=len-1;i>=0;i--)
> 		{
> 			printf("%d", dig[i]);
> 		}
> 	}
> };
> 
> bool IsSuffix(const BigNum& num, int* pat, int size)
> {
> 	if (size > num.len)
> 	{
> 		return false;
> 	}
> 
> 	for (int i = 0; i < size; i++)
> 	{
> 		if (num.dig[i] != pat[size - i - 1])
> 		{
> 			return false;
> 		}
> 	}
> 
> 	return true;
> }
> 
> bool Match(int* pat, int patlen, const BigNum& tmp, int last)
> {
> 	int i = 0;
> 	for (i = 0; i < tmp.len && last + i < patlen; i++)
> 	{
> 		//BigNum从高位比起
> 		if (tmp.dig[tmp.len-i-1] != pat[last + i])
> 		{
> 			return false;
> 		}
> 	}
> 
> 	return i == tmp.len || last + i == patlen;
> }
> 
> void MakeStr(int *pat, int len, std::vector<int>& a)
> {
> 	for(int i=0;i<len;i++)
> 	{
> 		a.push_back(pat[i]);
> 	}
> }
> 
> bool Match(std::vector<int>::iterator beginA, std::vector<int>::iterator endA,
> 	const std::vector<int>& strA)
> {
> 	int i=0;
> 	while(beginA<endA)
> 	{
> 		if(*beginA!=strA[i])
> 		{
> 			return false;
> 		}
> 		i++;
> 		beginA++;
> 	}
> 
> 	return true;
> }
> 
> void Concat(const std::vector<int>& strb, const std::vector<int>& stra,
> 	int pos,
> 	std::vector<int>& num)
> {
> 	int rearSize=stra.size()-(strb.size()-pos);
> 	num=strb;
> 	num.reserve(rearSize+strb.size());
> 	
> 	for(int i=stra.size()-rearSize;i<stra.size();i++)
> 	{
> 		num.push_back(stra[i]);
> 	}
> }
> 
> void FindSeperateTwoSegments(int patlen, int* pat, BigNum& ans, int& offset)
> {
> 	//枚举中间断开位置
> 	for(int i=0;i+1<patlen;i++)
> 	{
> 		std::vector<int> stra, strb;
> 		//两个串保存起来
> 		MakeStr(pat, i+1, stra);
> 		MakeStr(pat+i+1, patlen-i-1, strb);
> 
> 		//寻找一个前面的前缀等于后面的后缀的位置，然后把这两个串叠起来
> 		//枚举后面串对齐第一个串的首位置
> 		for(int pos=0;pos<=strb.size();pos++)
> 		{
> 			if(strb.size()-pos>stra.size())
> 			{
> 				//后面的串太短，覆盖不了前面串的后缀
> 				continue;
> 			}
> 
> 			if(Match(strb.begin()+pos, strb.end(), stra))
> 			{
> 				std::vector<int> num;
> 				Concat(strb, stra, pos, num);
> 				BigNum pre=BigNum(num.data(), num.size());
> 				if (IsSuffix(pre, pat, i + 1))
> 				{
> 					BigNum tmp = pre;
> 					++tmp;
> 					int last=i+1;
> 					
> 					if (Match(pat, patlen, tmp, last))
> 					{
> 						int newOffset = 1 + pre.len - (i + 1);
> 						int diff=pre.Compare(ans);
> 						if(diff<0)
> 						{
> 							ans=pre;
> 							offset=newOffset;
> 						}
> 						else if(diff==0 && newOffset<offset)
> 						{
> 							offset=newOffset;
> 						}
> 					}
> 					
> 				}
> 			}
> 		}
> 	}
> }
> 
> void FindSeperateSeveralSegments(int patlen, int* pat, BigNum& ans, int& offset)
> {
> 	//把pat分解成前后两部分，后面一部分是由n,n+1,n+2...堆起来的，那么后面的开头数字长度不能小于第一部分
> 	for (int i = 0; patlen - (i + 1) >= i + 1; i++)
> 	{
> 		if (pat[i + 1] == 0)
> 		{
> 			//首位数字必须非0
> 			continue;
> 		}
> 		//枚举后面数字[i+1,j]区间为第一个数字
> 		//j-i>=i+1
> 		for (int j = i + i + 1; j < patlen; j++)
> 		{
> 			printf("i=%d j=%d\n",i,j);
> 			BigNum head = BigNum(pat + i + 1, j - i);
> 			BigNum pre = head;
> 			--pre;
> 			printf("pre="); pre.print();
> 			cout<<endl;
> 
> 			//判断前面部分是否为head-1的后缀
> 			if (!IsSuffix(pre, pat, i + 1))
> 			{
> 				continue;
> 			}
> 
> 			printf("suffix success\n");
> 
> 			int last = i+1;
> 			BigNum tmp = head;
> 			//tmp一直++，把last后面的数字依依匹配，看看能不能配完
> 			while (last < patlen)
> 			{
> 				if (!Match(pat, patlen, tmp, last))
> 				{
> 					break;
> 				}
> 
> 				last += tmp.len;
> 				++tmp;
> 			}
> 
> 			printf("last=%d patlen=%d\n", last, patlen);
> 
> 			if (last >= patlen)//匹配成功
> 			{
> 
> 				int newOffset = 1 + pre.len - (i + 1);
> 				int diff=pre.Compare(ans);
> 
> 				printf("one solution = ");
> 				pre.print();
> 				
> 				printf(", offset=%d\n", newOffset);
> 				//记录一下现在的答案
> 				if (diff<0)
> 				{
> 					ans = pre;
> 					offset = newOffset;
> 				}
> 				else if(diff==0 && newOffset<offset)
> 				{
> 					offset=newOffset;
> 				}
> 			}
> 		}
> 	}
> }
> 
> BigNum Add(const BigNum& a, const BigNum& b)
> {
> 	BigNum c;
> 	c.clr();
> 	c.len=std::max(a.len, b.len);
> 
> 	for(int i=0;i<c.len;i++)
> 	{
> 		c.dig[i]=a.dig[i]+b.dig[i];
> 	}
> 
> 	for(int i=0;i<c.len;i++)
> 	{
> 		if(c.dig[i]>=10)
> 		{
> 			c.dig[i+1]+=c.dig[i]/10;
> 			c.dig[i]%=10;
> 		}
> 	}
> 
> 	if(c.dig[c.len])
> 	{
> 		c.len++;
> 	}
> 
> 	return c;
> }
> 
> void MulTen(BigNum& num)
> {
> 	for(int i=num.len;i>0;i--)
> 	{
> 		num.dig[i]=num.dig[i-1];
> 	}
> 	num.dig[0]=0;
> 	num.len++;
> }
> 
> int BitCount(int n)
> {
> 	if(n==0)
> 	{
> 		return 1;
> 	}
> 
> 	int len=0;
> 	while(n)
> 	{
> 		len++;
> 		n/=10;
> 	}
> 
> 	return len;
> }
> 
> BigNum Mul(const BigNum& a, int b)
> {
> 	BigNum c;
> 	c.clr();
> 	if(b==0)
> 	{
> 		return c;
> 	}
> 	c.len=a.len+BitCount(b);
> 	for(int i=0;i<a.len;i++)
> 	{
> 		c.dig[i]=a.dig[i]*b;
> 	}
> 
> 	for(int i=0;i<c.len;i++)
> 	{
> 		if(c.dig[i]>=10)
> 		{
> 			c.dig[i+1]+=c.dig[i]/10;
> 			c.dig[i]%=10;
> 		}
> 	}
> 
> 	while(c.len>1&& c.dig[c.len-1]==0)
> 	{
> 		c.len--;
> 	}
> 
> 	return c;
> }
> 
> BigNum Minus(const BigNum& a,const BigNum& b)
> {
> 	BigNum c;
> 	c.clr();
> 	c.len=a.len;
> 	for(int i=0;i<a.len;i++)
> 	{
> 		c.dig[i]=a.dig[i]-b.dig[i];
> 	}
> 
> 	for(int i=0;i<a.len;i++)
> 	{
> 		if(c.dig[i]<0)
> 		{
> 			c.dig[i]+=10;
> 			c.dig[i+1]--;
> 		}
> 	}
> 
> 	while(c.len>1&&c.dig[c.len-1]==0)
> 	{
> 		c.len--;
> 	}
> 
> 	return c;
> }
> 
> void CalcIndex(const BigNum& num, int offset, BigNum& pos)
> {
> 	pos.clr();
> 	BigNum nine;
> 	BigNum one;
> 	nine.clr();
> 	nine.dig[0]=9;
> 	one.clr();
> 	one.dig[0]=1;
> 	//先计算长度比num短的数字长度总和
> 	for(int bitLen=1;bitLen<num.len;bitLen++)
> 	{
> 		//长度为bitLen的有nine个，每个长度为bitLen
> 		BigNum length=Mul(nine,bitLen);
> 		printf("bitLen=%d\n", bitLen);
> 		printf("nine=");
> 		nine.print();
> 		std::cout<<endl;
> 		printf("length=");
> 		length.print();
> 		std::cout<<endl;
> 		pos=Add(pos, length);
> 		printf("tempPos=");
> 		pos.print();
> 		std::cout<<endl;
> 		MulTen(nine);
> 		MulTen(one);
> 	}
> 
> 	printf("small length = ");
> 	pos.print();
> 	std::cout<<std::endl;
> 
> 	//统计长度为num.len的个数，以及长度
> 	BigNum equalLengthNum=Minus(num, one);
> 
> 	BigNum otherLength=Mul(equalLengthNum, num.len);
> 	pos=Add(pos, otherLength);
> 
> 	pos.Add(offset);
> }
> 
> int main()
> {
> 	char str[512];
> 	int pat[512];
> 	int patlen = 0;
> 	while (cin.getline(str, 1024))
> 	{
> 		patlen = strlen(str);
> 		for (int i = 0; i < patlen; i++)
> 		{
> 			pat[i] = str[i] - '0';
> 		}
> 
> 		//一个初始解，也就是仅由于段组成的
> 		BigNum ans = BigNum(pat, patlen);
> 		int offset = 1;
> 
> 		if (ans.dig[ans.len - 1] == 0)
> 		{
> 			//最高位为0，需要添加一位,比如0，是10后面来的，01应该是101后面来的
> 			offset++;
> 			ans.dig[ans.len] = 1;
> 			ans.len++;
> 		}
> 
> 		//假设由若干个数字拼成，寻找答案
> 		FindSeperateSeveralSegments(patlen, pat, ans, offset);
> 
> 		//假设只由两个数字拼成，寻找答案
> 		FindSeperateTwoSegments(patlen, pat, ans, offset);
> 
> 		printf("ans=");
> 		ans.print();
> 		std::cout<<std::endl;
> 		printf("offset=%d\n", offset);
> 
> 		BigNum pos;
> 		CalcIndex(ans, offset, pos);
> 
> 		pos.print();
> 		cout<<endl;
> 	}
> 	return 0;
> }
> 
> /*
> http://poj.org/problem?id=1863
> Subnumber
> 要考虑前导0，一堆0的情况
> 
> 1
> ans=1
> offset=1
> 2
> ans=2
> offset=1
> 3
> ans=3
> offset=1
> 101
> ans=10
> offset=1
> 1234
> ans=1
> offset=1
> 234
> ans=2
> offset=1
> 11
> ans=11
> offset=1
> 12
> ans=1
> offset=1
> 13
> ans=13
> offset=1
> 41
> ans=41
> offset=1
> 10111
> ans=110
> offset=2
> 011
> ans=10
> offset=2
> 121
> ans=121
> offset=1
> 123412351236123712381239
> 
> 121314
> 
> 1234123
> 
> 23412
> 3412
> 
> */