UVA 11557 - Code Theft

題目鏈接

題意：給定一些代碼文本。然后在給定一個現有文本，找出這個現有文本和前面代碼文本，反復連續行最多的這些文本

思路：把每一行hash成一個值。然后對于每個文本計算最大匹配值，枚舉后綴。然后利用KMP去找就可以

代碼：

#include <cstdio> #include <cstring> #include <vector> #include <string> #include <iostream> #include <vector> using namespace std;typedef unsigned long long ull;const ull X = 123; const int N = 105;int n, next[1000005]; string name[N]; string s; vector<int> ans; vector<ull> code[N];void hash(string s, int u) {string ss = "";int l = 0, r = s.length() - 1, len = s.length();;while (s[l] == ' ' && l < len) l++;while (s[r] == ' ' && r >= 0) r--;for (int i = l; i <= r; i++) {ss += s[i];while (s[i] == ' ' && s[i + 1] == ' ' && i < r) i++;}if (ss == "") return;ull ans = 0;for (int i = ss.length() - 1; i >= 0; i--)ans = ans * X + ss[i];code[u].push_back(ans); }void build(int i) {code[i].clear();while (getline(cin, s) && s != "***END***") {hash(s, i);} }vector<ull> T;void getnext() {int N = T.size();next[0] = next[1] = 0;int j = 0;for (int i = 2 ; i <= N; i++) {while (j && T[i - 1] != T[j]) j = next[j];if (T[i - 1] == T[j]) j++;next[i] = j;} }int find() {int ans = 0;int N = code[n].size(), m = T.size(), j = 0;for (int i = 0; i < N; i++) {while (j && code[n][i] != T[j]) j = next[j];if (code[n][i] == T[j]) j++;ans = max(ans, j);if (j == m)return m;}return ans; }int cal(int u) {int ans = 0;int sz1 = code[u].size();for (int i = 0; i < sz1; i++) {T.clear();for (int j = i; j < sz1; j++)T.push_back(code[u][j]);getnext();ans = max(ans, find());}return ans; }void solve() {int Max = 0;ans.clear();for (int i = 0; i < n; i++) {int tmp = cal(i);if (tmp > Max) {Max = tmp;ans.clear();ans.push_back(i);}else if (tmp == Max) ans.push_back(i);}cout << Max;if (Max) {for (int i = 0; i < ans.size(); i++)cout << " " << name[ans[i]];}cout << endl; }int main() {while (cin >> n) {getchar();for (int i = 0; i < n; i++) {getline(cin, name[i]);build(i);}build(n);solve();}return 0; }

轉載于:https://www.cnblogs.com/gcczhongduan/p/5138461.html

總結

以上是生活随笔為你收集整理的UVA 11557 - Code Theft (KMP + HASH)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。