列表

详情


NC50344. L 语言

描述

标点符号的出现晚于文字的出现,所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。
一段文章T是由若干小写字母构成。一个单词W也是由若干小写字母构成。一个字典D是若干个单词的集合。我们称一段文章T在某个字典D下是可以被理解的,是指如果文章T可以被分成若干部分,且每一个部分都是字典D中的单词。
例如字典D中包括单词is,your,what,name,则文章whatisyourname是在字典D下可以被理解的,因为它可以分成4个单词:what,is,your,name,且每个单词都属于字典D,而文章whatisyouname在字典D下不能被理解,但可以在字典D’=D+you下被理解。这段文章的一个前缀whatis,也可以在字典D下被理解,而且是在字典D下能够被理解的最长的前缀。
给定一个字典D,你的程序需要判断若干段文章在字典D下是否能够被理解。并给出其在字典D下能够被理解的最长前缀的位置。

输入描述

输入文件第一行是两个正整数n和m,表示字典D中有n个单词,且有m段文章需要被处理。
之后的n行每行描述一个单词,再之后的m行每行描述一段文章。

输出描述

对于输入的每一段文章,你需要输出这段文章在字典D可以被理解的最长前缀的位置。

示例1

输入:

4 3
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

输出:

14
6
0

说明:

对于文章whatisyourname,整段文章whatisyourname都能被理解。
对于文章whatisyouname,前缀whatis能够被理解。
对于文章whaisyourname,没有任何前缀能够被理解

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

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;
}

上一题