trie求助
查看原帖
trie求助
382274
暗影之梦楼主2021/8/14 19:42
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string a,b,c;
int cntc;
int head;
const int maxn=1000001;
const int cset=26;
int trie[maxn][cset]={0};
int color[maxn]={0};
int vis[maxn];
int k=1;
int p;
int n,m;
int cnt;
int p1;
void insert(string s)
{
	int p=0;
	for(int i=0;i<cntc;++i)
	{
		int c;
		if(s[i]>='a'&&s[i]<='z') c=s[i]-'a';
		else c=s[i]-'A';
		if(!trie[p][c])
		{
			trie[p][c]=++cnt; 
		}
		p=trie[p][c]; 
	}
	color[p]=1;
}
int search(string s)
{
    int len=s.length();
    p=0;
    for(int i=0;i<len;i++)
	{
		int c;
		if(s[i]>='a'&&s[i]<='z') c=s[i]-'a';
		else c=s[i]-'A';
        if(!trie[p][c]) return 0;
        p=trie[p][c];
    }
    vis[p]++;
    return color[p]==1;
}
int main()
{
	cin>>a;
	insert(a);
	getline(cin,b);
	cout<<a<<endl;
	cout<<b<<endl;
	for(int i=0;i<b.length();i++)
	{
		if(b[i]==' ') 
		{
			cout<<cntc<<" "<<c<<endl;
			if(search(c)&&vis[p]==1) p1==p,cout<<head<<" ";
			cntc=0;
			head=i+1;
		}
		c[cntc]=b[i];
		cntc++;
	}
	if(!vis[p1]) cout<<-1;
	else cout<<vis[p1];
	return 0;
}
2021/8/14 19:42
加载中...