アルゴリズムtireツリー
1187 ワード
ACオートマチックを習うつもりですが、考えてみればtireツリーを勉強したほうがいいです.
tire数は1本の木で1つの文字列を表し、ノードから、ある文字列が終わるノードまで、経路はこの文字列であり、tire数内に1つの文字列があるかどうかを比較的効率的に検索することができます.
まず私のテンプレートを放します.
挿入するときは、挿入する文字に沿って挿入し続けるだけです.
クエリーは、クエリーする文字に沿って絶えずクエリーすればいいです.
このようにして、何も言うことはありません.コードが実現して自分で混乱しないでください.
tire数は1本の木で1つの文字列を表し、ノードから、ある文字列が終わるノードまで、経路はこの文字列であり、tire数内に1つの文字列があるかどうかを比較的効率的に検索することができます.
まず私のテンプレートを放します.
struct tire
{
int tot,root,child[max_node][max_char],sum;
bool vis[max_node];
tire()
{
memset(child,0,sizeof(child));
memset(vis,0,sizeof(vis));
root = tot = 1;
}
void insert(const char *str)
{
int lenn = strlen(str);
int tx = root;
for (int i = 1;i <= lenn;i++)
{
if (!child[tx][str[i - 1] - 'a'])
{
sum++;
child[tx][str[i - 1] - 'a'] = sum;
}
tx = child[tx][str[i - 1] - 'a'];
}
vis[tx] = 1;
}
bool query(const char *str)
{
int tx = root;
int lenn = strlen(str);
for (int i = 1;i <= lenn;i++)
{
if (!child[tx][str[i - 1] - 'a'])
{
return false;
}
tx = child[tx][str[i - 1] - 'a'];
}
if (!vis[tx]) return false;
return true;
}
};
配列の意味child i,jはi番点,文字jの子供の番号,visはあるノードが文字列の終点であるかどうかを示す.挿入するときは、挿入する文字に沿って挿入し続けるだけです.
クエリーは、クエリーする文字に沿って絶えずクエリーすればいいです.
このようにして、何も言うことはありません.コードが実現して自分で混乱しないでください.