KMP + 贪心

#include <iostream>
#include <string.h>
using namespace std;

int m;
const int maxn=100005;

char T[maxn],S[15][maxn];
struct node {
    int l,r;
    bool operator < (const node &a) const 
    {
        return r<a.r; //重载小于号，按右端点从小到大排序
    }
};
vector<node>st;  //保存区间
int ne[maxn];

void KMP(char p[], char s[], int n, int m)
{
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            //printf("%d ", i - n + 1);
            j = ne[j];
            st.push_back(node{i- n + 1,i});  
        }
    }
}

int main() 
{
    cin >> m;
    for(int i = 0; i < m; i++) cin >> S[i] + 1;
    cin >> T + 1;
    for(int i = 0; i < m; i++) {
        KMP(S[i], T, strlen(S[i] + 1), strlen(T + 1));
    }

    //贪心算法
    sort(st.begin(),st.end());
    int last=-1,ans=0;
    for(int i = 0; i < st.size(); i++)
     {
        if(st[i].l > last) 
        {
            last=st[i].r;
            ans++;
        }
    }
    cout << ans;
    return 0;
}