String text

nowcode 15165

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    s = " " + s;
    vector<int> nxt(n + 1);
    for (int i = 2; i <= n; i++) {
        nxt[i] = nxt[i - 1];
        while (nxt[i] && s[nxt[i] + 1] != s[i]) {
            nxt[i] = nxt[nxt[i]];
        }
        nxt[i] += (s[nxt[i] + 1] == s[i]);
    }

    int cnt = count(nxt.begin() + 1, nxt.end(), nxt[n]);
    if (nxt[n] && cnt >= 2) {
        for (int i = 1; i <= nxt[n]; i++) {
            cout << s[i];
        }
    } else {
        if (nxt[nxt[n]] == 0) {
            cout << "Just a legend\n";
            return;
        }
        for (int i = 1; i <= nxt[nxt[n]]; i++) {
            cout << s[i];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

nowcoder 16638

跑n + m次KMP(面向对象会很好用), 然后二维单调栈就可以解决

struct KMP{
    int n;
    string p;
    vector<int> ne;
    KMP(){}
    KMP(string &s){init(s);}
    void init(string &s){
        n = s.size();
        p = s;
        ne.resize(n);
        ne[0] = -1;
        for(int i = 1,j = -1;i < n;i++){
            while(j != -1 && p[i] != p[j + 1])j = ne[j];
            if(p[i] == p[j + 1])j++;
            ne[i] = j;
        }
    }
    vector<int> match(string &s){
        int m = s.size();
        vector<int> res;
        for(int i = 0,j = -1;i < m;i++){
            while(j != -1 && s[i] != p[j + 1])j = ne[j];
            if(s[i] == p[j + 1])j++;
            if(j == n - 1)res.push_back(i - n + 1),j = ne[j];
        }
        return res;
    }
};

void solve(){
    int n,m;
    cin >> n >> m;
    vector<string> a(n);
    vector<vector<LL>> b(n,vector<LL>(m));
    for(int i = 0;i < n;i++)cin >> a[i];
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> b[i][j];
        }
    }
    map<int,int> mp;
    for(int i = 0;i < n;i++){
        KMP t(a[i]);
        for(int j = t.ne[m - 1];j != -1;j = t.ne[j]){
            mp[m - j - 1]++;
        }
        mp[m]++;
    }
    int r = 0,c = 0;
    for(auto it : mp){
        if(it.second >= n){
            r = it.first;
            break;
        }
    }
    mp.clear();
    for(int j = 0;j < m;j++){
        string s;
        for(int i = 0;i < n;i++){
            s += a[i][j];
        }
        KMP t(s);
        for(int j = t.ne[n - 1];j != -1;j = t.ne[j]){
            mp[n - j - 1]++;
        }
        mp[n]++;
    }
    for(auto it : mp){
        if(it.second >= m){
            c = it.first;
            break;
        }
    }

    vector<vector<LL>> d(n,vector<LL>(m - r + 1));
    for(int i = 0;i < n;i++){
        deque<int> q;
        for(int j = 0;j < m;j++){
            while(q.size() && j - q.front() + 1 > r)q.pop_front();
            while(q.size() && b[i][q.back()] <= b[i][j])q.pop_back();
            q.push_back(j);
            if(j >= r - 1)d[i][j - r + 1] = b[i][q.front()];
        }
    }
    LL res = 1e18;
    for(int j = 0;j < m - r + 1;j++){
        deque<int> q;
        for(int i = 0;i < n;i++){
            while(q.size() && i - q.front() + 1 > c)q.pop_front();
            while(q.size() && d[q.back()][j] <= d[i][j])q.pop_back();
            q.push_back(i);
            if(i >= c - 1){
                res = min(res,(r + 1) * (c + 1) * d[q.front()][j]);
            }
        }
    }   
    cout << res << endl;

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

luogu 3375

KMP板子

int kmp[MAXN];
int la,lb,j; 
char a[MAXN],b[MAXN];
int main()
{
    cin>>a+1;
    cin>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for (int i=2;i<=lb;i++)
	   {     
	   while(j&&b[i]!=b[j+1])
        j=kmp[j];    
       if(b[j+1]==b[i])j++;    
        kmp[i]=j;
       }
    j=0;
    for(int i=1;i<=la;i++)
	   {
          while(j>0&&b[j+1]!=a[i])
           j=kmp[j];
          if (b[j+1]==a[i]) 
           j++;
          if (j==lb) {cout<<i-lb+1<<endl;j=kmp[j];}
       }

    for (int i=1;i<=lb;i++)
    cout<<kmp[i]<<" ";
    return 0;
}

nowcoder 14964

kmp的一个变换

std::vector<int> KMP(const std::vector<int> &s) {
    int n = s.size();
    std::vector<int> f(n + 1);
    for (int i = 1, j = 0; i < n; i++) {
        while (j && s[i] != s[j]) {
            j = f[j];
        }
        j += (s[i] == s[j]);
        f[i + 1] = j;
    }
    return f;
}
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n), b(m);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] %= k;
    }
    for(int i = 0; i < m; i++) {
        cin >> b[i];
        b[i] %= k;
    }

    vector<int> difa(n - 1), difb(m - 1);
    for(int i = 0; i < n - 1; i++) {
        difa[i] = a[i] - a[i + 1];
        if(difa[i] < 0) {
            difa[i] += k;
        }
    }
    for(int i = 0; i < m - 1; i++) {
        difb[i] = b[i] - b[i + 1];
        if(difb[i] < 0) {
            difb[i] += k;
        }
    }

    auto nxt = KMP(difb);
    int ans = 0;
    for(int i = 0, j = 0; i < n - 1; i++) {
        while(j && (difa[i] + difb[j]) % k != 0) j = nxt[j];
        if((difa[i] + difb[j]) % k == 0)j++;
        if(j == m - 1) {
            ans++;
            j = nxt[j];
        }
    }

    cout << ans << "\n";
}
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    int tt = 1;
    std::cin >> tt;
    while (tt--)
        solve();
}

nowcoder 51120

可持久化01trie,query前缀就好了

struct Trie_per {
    static constexpr int SIZE = 2;
    static constexpr int width = 24;  // 值域小于2的width次方
    struct Node {
        int cnt;
        array<int, SIZE> next;
        Node() : cnt{0}, next{} {}
    };
    vector<Node> t;
    vector<int> ver;
    Trie_per() { init(); }
    void init() {
        t.assign(2, {});
        ver.resize(1);
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int add(int pre, const vector<int> &a) {
        int cur = newNode();
        int p = pre, q = cur;
        t[q] = t[p];
        for (auto x : a) {
            t[q].next[x] = newNode();
            p = next(p, x);
            q = next(q, x);
            t[q] = t[p];
            t[q].cnt++;
        }
        return cur;
    }
    int add(int pre, int x) {  // 转成01vector
        vector<int> a;
        for (int i = width - 1; i >= 0; i--) {
            a.push_back((x >> i) & 1);
        }
        return add(pre, a);
    }
    void add(int x) {  // 外部接口
        int pos = add(ver.back(), x);
        ver.push_back(pos);
    }
    // 查询x在版本(l,r]中和哪个数异或最大
    int querymx(int l, int r, int x) {  // 传l-1进来
        int res = 0;
        int p = ver[l], q = ver[r];
        for (int i = width - 1; i >= 0; i--) {
            int u = (x >> i) & 1;
            int nxp = t[p].next[u ^ 1], nxq = t[q].next[u ^ 1];
            if (t[nxq].cnt - t[nxp].cnt > 0) {
                res |= 1 << i;
                u ^= 1;
            }
            p = t[p].next[u];
            q = t[q].next[u];
        }
        return res;
    }
    int size() { return t.size(); }
    int cnt(int p) { return t[p].cnt; }
    int next(int p, int x) { return t[p].next[x]; }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), sum(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] ^ a[i];
    Trie_per tr;
    tr.add(0);
    for (int i = 1; i <= n; i++) tr.add(sum[i]);
    for (int i = 1; i <= m; i++) {
        string op;
        cin >> op;
        if (op == "A") {
            int x;
            cin >> x;
            sum.push_back(sum.back() ^ x);
            tr.add(sum.back());
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            int res = tr.querymx(l - 1, r, sum.back() ^ x);
            cout << res << endl;
        }
    }
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}