#1282
这题是字符串匹配问题,用了kmp算法
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int nextarray[1000000];
int pattern[1000000];
int target[1000000];
void setNextarray(int n){
nextarray[0] = 0;
int k = 0;
for (int i = 1; i < n; i++){
k = nextarray[i-1];
while (pattern[i] != pattern[k] && k != 0){
k = nextarray[k - 1];
}
if (pattern[i] == pattern[k]){
nextarray[i] = k + 1;
}
else{
nextarray[i] = 0;
}
}
}
void kmp(int m,int n){
setNextarray(n);
int i = 0;
int k = 0;
int pos = 0;
while (i < m){
while (pattern[pos] == target[i + k]){
pos++;
k++;
if (k == n){
cout << i << endl;
return;
}
}
if (k != 0){
i = i + (k - nextarray[k - 1]);
k = nextarray[k - 1];
pos = k;
}
else{
i++;
k = 0;
pos = 0;
}
}
cout << "no solution" << endl;
}
int main(){
int n;
int m;
while (scanf("%d", &n) != EOF){
for (int i = 0; i < n; i++){
cin >> pattern[i];
}
cin >> m;
for (int i = 0; i < m; i++){
cin >> target[i];
}
kmp(m,n);
}
return 0;
}