Lutece 2211 qh与复读机I

题目链接: https://acm.uestc.edu.cn/problem/qhyu-fu-du-ji-i/description

分析:

第一眼,查询有多少个相同,第一反应hash。

然后写了个hash交上去,不出所料的T了。

仔细分析问题后发现,只要用Trie即可,正着和反着都来一个。

用数组来写Trie是更好的,但是不想抄板子,想自己手写一个,于是就写了个指针版的Trie。

内存超的头都没了,以后一定用数组版的。

代码:

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <set>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INF64 = 3e18;
const unsigned long long HASHBASE=1222827239ull;
/////////////////////////
struct node
{
    int num=0;
    node *child[26];
};
void insert(string str, node *root)
{
    node *insertroot = root;
    int len = str.length();
    for(int i=0;i<len;++i)
    {
        if( (*insertroot).child[str[i]-'a'] == NULL)
        {
            (*insertroot).child[str[i]-'a'] = new node();
        }
        insertroot = (*insertroot).child[str[i]-'a'];
        (*insertroot).num++;
    }
}
int query(string str, node *root)
{
    node *queryroot = root;
    int len = str.length();
    for(int i=0;i<len;++i)
    {
        if( (*queryroot).child[str[i]-'a'] == NULL)
        {
            return 0;
        }
        queryroot = (*queryroot).child[str[i]-'a'];
    }
    return (*queryroot).num;
}
node *root1 = new node();
node *root2 = new node();
/////////////////////////
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin>>n;
    string tmp1,tmp2;
    for(int i=0;i<n;++i)
    {
        cin>>tmp2;
        tmp1 = tmp2;
        reverse(tmp2.begin(),tmp2.end());
        cout<<query(tmp1,root1)<<" "<<query(tmp2,root2)<<endl;
        insert(tmp1,root1);insert(tmp2,root2);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注