1282 Soj-1282 这题是字符串匹配问题,用了Horspool算法 #include<iostream> #include<stdio.h> #include<string.h> using namespace std; int table[256];//char 8 bits int pattern[1000000];//模式串 int target[1000000];//目标串 void shifttable(int n){ //important for (int i = 0; i < 256; i++){ table[i] = n; } for (int i = 0; i < n-1; i++){ table[pattern[i]] = n - i - 1; } } //String Matching --Horspool Algorithm void Horspool(int m,int n){ shifttable(n); int i = n - 1; int k = n - 1; while (i < m){ int pos = i; while (target[pos] == pattern[k]){ if (k == 0){ cout << pos << endl; return; } pos--; k--; } i += table[target[i]]; k = n - 1; } 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]; } Horspool(m,n); } return 0; } ← Previous Post Next Post →