HDU1936 [贪心+KMP] 点的区间覆盖

每一行对话分别取匹配所有的表情

这样是一个n**2的匹配，可以用KMP 找出每行对话中的每个表情的左右端点

这样相当于就是问用最少多少个点可以覆盖所有的区间(每个区间中放一个点表示覆盖)

贪心按右端点升序排列相同时左端点也升序(这里其实没有影响但是按照匹配上来讲应该按照升序)

--理由：

--> 如果当前所指区间的后面两个区间的右端点相同那么应该是先比较左端点较小的那个区间

但是因为后面两个区间的右端点相同那么一定是相互覆盖的所以对结果没有影响

然后 if (strict[crt].r < strict[next]) .l ) //区间不重叠

　　　{ans++; crt = next;}

代码君：

#include <bits/stdc++.h>

#include <string.h>

#include <iostream>

#include <stdio.h>

using namespace std;

const int MAXN = ;

const int MAXLEN = ;

char emo[MAXN][MAXLEN];

char str[MAXLEN];

struct S

{

    int l, r;

    S() {}

    S(int l, int r) : l(l), r(r) {}

    bool operator < (S s1) const

    {

        if (r != s1.r) return r < s1.r;

        return l < s1.l;

    }

};

int n, m;

int nxt[MAXN << ];

vector<S> v;

void kmp_pre(char t[])

{

    int j, k;

    int tlen = strlen(t);

    k = -, j = ; nxt[] = -;

    while (j < tlen)

    {

        if (k == - || t[j] == t[k]) nxt[++j] = ++k;

        else k = nxt[k];

    }

}

vector<int> kmp(char s[], char t[])

{

    int slen = strlen(s), tlen = strlen(t);

    vector<int> ret;

    int i = , j = ;

    kmp_pre(t);

    while (i < slen)

    {

        if (j == - || s[i] == t[j])

        {

            i++;

            j++;

        }

        else j = nxt[j];

        if (j == tlen)

        {

            ret.push_back(i-);

            j = nxt[j];

        }

    }

    return ret;

}

int lidx[MAXN], ridx[MAXN];

int main()

{

    //freopen("in.txt", "r", stdin);

    while (~scanf("%d%d", &n, &m))

    {

        if (!n && !m) break;

        int ans = ;

        for (int i = ; i < n; i++)

        {

            scanf("%s", emo[i]);

        }

        getchar();

        for (int i = ; i < m; i++)

        {

            gets(str);

            v.clear();

            for (int j = ; j < n; j++)

            {

                vector<int> pos;

                int len = strlen(emo[j]);

                pos = kmp(str, emo[j]);

                for (int k = ; k < pos.size(); k++)

                {

                    v.push_back(S(pos[k]-len+, pos[k]));

                }

            }

            sort(v.begin(), v.end());/*

            for (int i = 0; i < v.size(); i++) cout << v[i].l << " " << v[i].r << endl;

            return 0;*/

            int crt = ;

            if (!v.empty()) ans++;

            for (int j = ; j < v.size(); j++)

            {

                if (v[j].l > v[crt].r)

                {

                    crt = j;

                    ans++;

                }

            }

        }

        cout << ans << endl;

     }

    return ;

}

巴特西

HDU1936 [贪心+KMP] 点的区间覆盖

最新文章

热门文章