当前位置:网站首页>P2922 [USACO08DEC]Secret Message G(Trie)

P2922 [USACO08DEC]Secret Message G(Trie)

2021-08-10 08:44:52 wx6110fa547fd20

P2922 [USACO08DEC]Secret Message G(Trie)

Trie It can be used to count the number of strings, prefixes and matches .

The question : Given m m m Text strings , n n n Pattern strings .

Find the maximum prefix of each pattern string and how many text strings are the same .

Yes m m m Construct a text string T r i e Trie Trie, And then every time O ( n ) O(n) O(n) Just search .

build T r i e Trie Trie when , Maintain two variables , One is the number of times through the node s s s, One is the number of strings ending with this node e d ed ed.

Then when calculating the contribution , Just run through the string , Add... Every time ed, If the traversal is not completed, the sum That's the answer. , Otherwise, add a[p].s-a[p].ed,a[p].s It includes a[p].ed, and a[p].ed It's been counted before , So just add the number of text strings whose true prefix is the pattern string .

code

// Problem: P2922 [USACO08DEC]Secret Message G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2922
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2021-07-06 15:48:40
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=5e4+5,M=5e5+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
struct node{
	int nt[2],s,ed;
}a[M];
int b[N],len,cnt;
void ins(){
	int p=0;
	for(int j=1;j<=len;j++){
		if(!a[p].nt[b[j]]) a[p].nt[b[j]]=++cnt;
		p=a[p].nt[b[j]];
		a[p].s++;
	}
	a[p].ed++;
}
ll que(){
	ll ans=0;
	int p=0;
	bool ok=true;
	for(int i=1;i<=len;i++){
		if(!a[p].nt[b[i]]){
			ok=0;break;
		} 
		p=a[p].nt[b[i]];
		ans+=a[p].ed;
	}
	return ok?ans+a[p].s-a[p].ed:ans;
}
int main(){
	int n,m;scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++){
		scanf("%d",&len);
		for(int j=1;j<=len;j++) scanf("%d",&b[j]);
		ins();
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&len);
		for(int j=1;j<=len;j++) scanf("%d",&b[j]);
		printf("%lld\n",que());
	}
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810084312070L.html

随机推荐