NC50344. L 语言
描述
输入描述
输入文件第一行是两个正整数n和m,表示字典D中有n个单词,且有m段文章需要被处理。
之后的n行每行描述一个单词,再之后的m行每行描述一段文章。
输出描述
对于输入的每一段文章,你需要输出这段文章在字典D可以被理解的最长前缀的位置。
示例1
输入:
4 3 is name what your whatisyourname whatisyouname whaisyourname
输出:
14 6 0
说明:
对于文章whatisyourname,整段文章whatisyourname都能被理解。C++(g++ 7.5.0) 解法, 执行用时: 170ms, 内存消耗: 16688K, 提交时间: 2023-07-12 20:47:31
#include<bits/stdc++.h> #include<stack> #include<map> using namespace std; typedef long long ll; typedef pair<int, int> PII; const int N = 2e6 + 10; int son[N][26], cnt[N], idx; char s[N]; int dp[N]; void insert(char* str) { int p = 0; for (int i = 0; str[i]; i++) { int u = str[i] - 'a'; if (!son[p][u])son[p][u] = ++idx; p = son[p][u]; } cnt[p] = 1; } void query(char* str, int len) { memset(dp, 0, sizeof dp); int ans = 0; for (int i = 0; i <= len; i++) { if (dp[i] != i)continue; int p = 0; for (int j = i+1; j <= len; j++) { int u = str[j] - 'a'; if (!son[p][u])break; p = son[p][u]; if (cnt[p])ans = max(ans, j), dp[j] = j; } } cout << ans << endl; } int main(){ int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> s; insert(s); } while (m--) { cin >> s + 1; int len = strlen(s + 1); query(s, len); } return 0; }
C++14(g++5.4) 解法, 执行用时: 114ms, 内存消耗: 3232K, 提交时间: 2019-12-09 18:36:51
#include<bits/stdc++.h> using namespace std; const int MAXN = 11*26; struct Node { int val; int ch[26]; }; Node nodes[MAXN]; int sz; void insert(string s) { int cur = 0; for (auto ch: s) { int id = ch - 'a'; int &nxt = nodes[cur].ch[id]; if (nxt == 0) nxt = ++sz; cur = nxt; } nodes[cur].val = true; } int main() { ios::sync_with_stdio(false); int n, m; cin >> n >> m; while (n--) { string s; cin >> s; insert(s); } while (m--) { string s; cin >> s; vector<bool> dp(s.size() + 1); dp[0] = true; int best = 0; for (int i = 0; i < s.size(); i++) if (dp[i]) { int j = i; int cur = 0; while (j < s.size()) { int id = s[j] - 'a'; int nxt = nodes[cur].ch[id]; // cout << i << " " << j << " " << nxt << endl; if (nxt == 0) break; cur = nxt; j++; if (nodes[cur].val) dp[j] = true, best = max(best, j); } } cout << best << endl; } }
C++ 解法, 执行用时: 148ms, 内存消耗: 4428K, 提交时间: 2022-02-04 13:10:22
#include<bits/stdc++.h> using namespace std; string s; int trie[10401][26],cnt; bool flag[10401],d[2000002]; void f(int i){ int rt = 0; for (;s[i];i++){ rt = trie[rt][s[i] - 'a']; if (!rt)return; if (flag[rt])d[i + 1] = 1; } } int main(){ int n,m,len,rt,*p,ans,i; cin>>n>>m; while (n--){ cin>>s; len = s.length(); rt = 0; for (i = 0;i < len;i++){ p = &trie[rt][s[i] - 'a']; if (!*p)*p = ++cnt; rt = *p; } flag[rt] = 1; } while (m--){ memset(d,0,sizeof(d)); cin>>s; ans = 0; f(0); for (i = 1;s[i];i++) if (d[i]){ f(i); ans = i; } if (d[i])ans = i; cout<<ans<<endl; } return 0; }