题解 | #子串#

#include<algorithm>
using namespace std;
int n, ne[5010100];
string s, k, t;

 string work(int nums, int k)
{
	string str = "";
	while (nums)
	{
		int m = nums % k;
		if (m < 10)
		{
			str += m + '0';
		}
		else
		{
			str += m + 'A'-10;
		}
		nums /= k;
	}
	reverse(str.begin(), str.end());
	return str;
}

int main()
{
	cin >> n;
	cin >> t;
	ne[0] = -1;
	for (int i = 1, j = -1; i < t.size(); i++)
	{
		while (j>=0 && t[i] != t[j + 1]) j = ne[j];
		if (t[i] == t[j + 1]) j++;
		ne[i] = j;
	}
	for (int k = 2; k <= 16; k++)
	{
		s = "";
		for (int i = 1; i <= n; i++)
		{
			s += work(i, k);
		}

		for (int i = 0, j = -1; i < s.size(); i++)
		{
			while (j>=0 && s[i] != t[j + 1]) j = ne[j];
			if (s[i] == t[j + 1]) j++;
			if (j == t.size()-1)
			{
				cout << "yes" << endl;
				return 0;
			}
		}
	}
	cout << "no" << endl;
	return 0;
}