算法1

(字典树) $O(n * 10)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define PI  acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 3e5+5;
int mod = 1e9 +7;
int n,m,k;
int tr[205 * 26][26];
bool f[maxn];
bool d[maxn];
int idx;
void insert(string s){
    int p = 0;
    int len = s.length();
    for(int i = 0 ; i < len ; ++i ){
        int t = s[i] - 'A';
        if(!tr[p][t]) tr[p][t] = ++idx;
        p = tr[p][t];
    }
    d[p] = true;
}
string t,s;

bool query(int ed){
    int p = 0;
    for(int i = ed ; i >= ed - 10 && i >= 0; --i ){
        int t = s[i] - 'A';
        if(!tr[p][t]) return false;
        else{
            p = tr[p][t];
            if(d[p] && f[i]) return true;
        }
    }
    return false;
}

void solve(){
    while(cin >> t,t != "."){
        reverse(t.begin(),t.end());
        insert(t);
    }
    string line;
    while(cin >> line) s += line;
    f[0] = true;
    n = s.length();
    int res = 0;
    for(int i = 1 ; i <= n ; ++i ){
        if(query(i - 1)){
            f[i] = true;
            res = i;
        }
    }
    cout << res << endl;
}

signed main(){
    IOS;
    solve();
    return 0;
}
/*
*
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/