学步园

1.KMP算法：http://blog.csdn.net/chenhq1991/article/details/7830193

2.因为题目说说的60000的长度是 code 的长度，主串的长度未知，所以要开大点

3.有了KMP算法，这道题就很简单了，但是KMP对我来说的确很难理解

#include<iostream>
#include<vector>
using namespace std;

int code_dimension;
int code[60000];
int protection_dimension;
int protection[1000000];//坑爹
int Next[60000];

void getNext()
{
	int j,k;
	Next[0] = -1;
	j = 0;//j 为主串下标
	k = -1;//k 为子串下标
	while(j < code_dimension - 1)
	{
		if(k == -1 || code[j] == code[k])
		{
			j++;
			k++;
			Next[j] = k;//next[1] = 0;
		}
		else
		{
			k = Next[k];
		}
	}

}

int KMPMatch( )
{
	getNext();
	int i = 0;//为主串的下标
	int j = 0;//为子串的下标
	while(i < protection_dimension)
	{
		if(j == -1 || protection[i] == code[j])//j = -1的情况就是匹配的子串要从头开始
		{
			i++;
			j++;
		}
		else
		{
			j = Next[j];//protection[i] != code[j]
		}

		if(j == code_dimension)//匹配结束
			return i - code_dimension;
	}
	return -1;//表示匹配不成功
}

int main()
{
	
	while(cin >> code_dimension && code_dimension != 0)
	{
		
		for(int i = 0; i < code_dimension; i++)
		{
			cin >> code[i];
		}

		cin >> protection_dimension;
		for(int i = 0; i < protection_dimension; i++)
		{
			cin >> protection[i];
		}
		int index = KMPMatch();
		if(index != -1)
			cout << index << endl;
		else
			cout << "no solution" << endl;
	}
	return 0;
}