// 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] --;
		}

		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 = 0; i < len; 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] ++;
		}

		if (dig[len])
		{
			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++)
	{
		if (tmp.dig[i] != 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++)
		{
			BigNum head = BigNum(pat + i + 1, j - i);
			BigNum pre = head;
			--pre;
			//判断前面部分是否为head-1的后缀
			if (!IsSuffix(pre, pat, i + 1))
			{
				continue;
			}

			int last = j + 1;
			BigNum tmp = head;
			//tmp一直++，把last后面的数字依依匹配，看看能不能配完
			while (last < patlen)
			{
				++tmp;
				if (!Match(pat, patlen, tmp, last))
				{
					break;
				}

				last += tmp.len;
			}

			if (last >= patlen)//匹配成功
			{
				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;
				}
			}
		}
	}
}

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);
	}
	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
*/

• test data (312) yygy 2023-05-12 23:26:37
  • Re:test data (8434) yygy 2023-05-13 13:00:27
    • 写了12K的代码，1A了，高兴。 (9572) yygy 2023-05-14 21:29:43