// 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

*/

• 写了12K的代码，1A了，高兴。 (9572) yygy 2023-05-14 21:29:43