一.P2580 于是他錯誤的點名開始了

?

?

這道題也類似于模版題，只要我們熟悉插入和查找的過程，一樣可以解決，這里只要注意一下第一次出現和其它次出現所輸出是不一樣的，這里我們只要在查找函數中返回不同的值，這樣就可以解決了。

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int n, m, id, ans, num;
int f[N][27], cnt[N];   //f數組為建樹用，cnt數組記錄插入次數
bool vis[N];    //標記數組
char s[N];void insert(char s[])   //插入函數
{int p = 0;  //p指針指向根節點for (int i = 0; s[i]; i++) {int q = s[i] - 'a' + 1;if (!f[p][q]) f[p][q] = ++id;  //如果沒有該節點，就新建一個p = f[p][q];    //繼續往下插入}vis[p] = true;    //插入完成，為下面查詢時做鋪墊
}int find(char s[])    //查找函數，注意這里要返回0,1,2三個值代表不同狀態
{int p = 0;for (int i = 0; s[i]; i++) {int q = s[i] - 'a' + 1;if (!f[p][q]) return 0;   //如果沒有查找到該字符，退出p = f[p][q];}if (!vis[p]) return 0;   //沒有查找到該字符串if (cnt[p]==0) {         //找到該字符串，但要討論是第幾次查到++cnt[p];return 1;}return 2;
}
int main()
{memset(vis, false, sizeof(vis));memset(cnt, 0, sizeof(cnt));cin >> n;for (int i = 1; i <= n; i++) {cin >> s;insert(s);}cin >> m;for (int i = 1; i <= m; i++) {cin >> s;int k = find(s);if (k == 0)                   //如果沒有找到cout << "WRONG" << endl;if (k == 1)                   //如果第一次找到cout << "OK" << endl;if (k == 2)                   //如果不是第一次找到cout << "REPEAT" << endl;}return 0;
}

---

二.P1481 魔族密碼

?

?對于這題我們只需要進行插入操作就可以，不需要進行查找操作，準確來說應該是在插入過程中進行查詢，我們只需要在一個單詞的末尾加上一個cnt數組記錄插入單詞末尾的次數后續的插入如果經過這個單詞末尾（也就是能夠連接起來），我們加上cnt[p],最后比較出最大的再+1就可以了

#include<bits/stdc++.h>
using namespace std;
#define N 2005
int f[N][27], cnt[N];
char s[N];
int n, m, sum, ans, id;int solve(char s[])
{int p = 0;    //p頭指針，指向根節點int ans1 = 0;for (int i = 0; s[i]; i++){int q = s[i] - 'a' + 1;if (!f[p][q])f[p][q] = ++id;  //如果不存在該節點，創造該節點p = f[p][q];ans1 += cnt[p];  //如果能夠連接在一起，詞鏈加1}cnt[p]++;     //單詞末尾記錄ans = max(ans, ans1);   //找到最長詞鏈return ans;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++) {cin >> s;sum = solve(s);}cout << sum+1 << endl;   //加一是因為最開始的那個起始單詞沒有納入return 0;
}