201809-3 元素选择器

思路

这道题主要还是学一下利用栈来模拟DFS的过程。只需要顺序遍历整个文本，然后对于不是此文本父节点的点弹出栈即可。同样，这个点要匹配的字符串的位置和父节点要匹配的字符串的位置相同。注意一下，如果父节点已经可以匹配了，那么这个节点还是要匹配最后一个字符串。非常牛呀这个思路，YCW YYDS！

代码

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n, m;
vector strs;

struct Node
{
    int tab;
    string tag, id;
    int k;  // 当前节点最多可以匹配到第几个位置

    Node(string str)
    {
        int i = 0;
        while (str[i] == '.') i ++ ;
        tab = i;
        while (i < str.size() && str[i] != ' ')
            tag += tolower(str[i ++ ]);
        i ++ ; // 过滤掉空格
        while (i < str.size()) id += str[i ++ ];
        k = 0;
    }
    bool check(string& word)
    {
        if (word[0] == '#') return word == id;
        return word == tag;
    }
};

void work(vector& ws)
{
    vector res;
    stack stk;
    for (int i = 0; i < strs.size(); i ++ )
    {
        string str = strs[i];
        Node t(str);
        while (stk.size() && stk.top().tab >= t.tab) stk.pop();
        if (stk.size()) t.k = stk.top().k;
        if (t.k == ws.size()) t.k -- ;
        if (t.check(ws[t.k]))
        {
            t.k ++ ;
            if (t.k == ws.size()) res.push_back(i + 1);
        }
        stk.push(t);
    }
    cout << res.size();
    for (auto x: res) cout << ' ' << x;
    cout << endl;
}

int main()
{
    cin >> n >> m;
    getchar();
    string str;
    while (n -- )
    {
        getline(cin, str);
        strs.push_back(str);
    }
    while (m -- )
    {
        getline(cin, str);
        stringstream ssin(str);
        vector ws;
        while (ssin >> str)
        {
            if (str[0] != '#')
                for (auto& c: str)
                    c = tolower(c);
            ws.push_back(str);
        }
        work(ws);
    }
    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/893996/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。