SUBSTR - Xâu con

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>

const int N = 2000006;

using namespace std;

string s, p;
int Z[N];

void buildZ(const string &s, int Z[]) {
  int n = s.size();
  Z[0] = 0; int l = 0, r = 0;
  for (int i = 1; i < n; ++i) {
    if (r < i) {
      l = r = i;
      while (r < n && s[r - l] == s[r]) ++r;
      Z[i] = r - l; --r;
    } else {
      int k = i - l;
      if (Z[k] < r - i + 1) {
        Z[i] = Z[k];
      } else {
        l = i;
        while (s[r - l] == s[r]) ++r;
        Z[i] = r - l; --r;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("SUBSTR.in", "r", stdin);
  #endif
  cin >> s >> p;
  s = p + '#' + s;
  buildZ(s, Z);
  for (int i = p.size() + 1; i < int(s.size()); ++i)
  if (Z[i] >= int(p.size()))
    cout << i - int(p.size()) << ' ';
}

Download