#1282 ###Soj-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; } ← Previous Post Next Post →