Substring Search - VietMX's Blog

You are given a permutation $p$ consisting of exactly $26$ integers from $1$ to $26$ (since it is a permutation, each integer from $1$ to $26$ occurs in $p$ exactly once) and two strings $s$ and $t$ consisting of lowercase Latin letters.

A substring $t’$ of string $t$ is an occurence of string $s$ if the following conditions are met:

$|t’| = |s|$;
for each $i \in [1, |s|]$, either $s_i = t’_i$, or $p_{idx(s_i)} = idx(t’_i)$, where $idx(c)$ is the index of character $c$ in Latin alphabet ($idx(\text{a}) = 1$, $idx(\text{b}) = 2$, $idx(\text{z}) = 26$).

For example, if $p_1 = 2$, $p_2 = 3$, $p_3 = 1$, $s = \text{abc}$, $t = \text{abcaaba}$, then three substrings of $t$ are occurences of $s$ (they are $t’ = \text{abc}$, $t’ = \text{bca}$ and $t’ = \text{aba}$).

For each substring of $t$ having length equal to $|s|$, check if it is an occurence of $s$.

Input

The first line contains $26$ integers $p_1$, $p_2$, …, $p_{26}$ ($1 \le p_i \le 26$, all these integers are pairwise distinct).

The second line contains one string $s$, and the third line contains one string $t$ ($2 \le |s| \le |t| \le 2 \cdot 10^5$) both consisting of lowercase Latin letters.

Output

Print a string of $|t| – |s| + 1$ characters, each character should be either 0 or 1. The $i$-th character should be 1 if and only if the substring of $t$ starting with the $i$-th character and ending with the $(i + |s| – 1)$-th character (inclusive) is an occurence of $s$.

Example

input

2 3 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
abc
abcaaba

output

Solution:

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int md = 998244353;

inline void add(int &x, int y) {
x += y;
if (x >= md) {
x -= md;
}
}

inline void sub(int &x, int y) {
x -= y;
if (x < 0) {
    x += md;
  }
}

inline int mul(int x, int y) {
  return (long long) x * y % md;
}

inline int power(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = mul(x, x)) {
if (y & 1) {
res = mul(res, x);
}
}
return res;
}

inline int inv(int a) {
a %= md;
if (a < 0) {
    a += md;
  }
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  if (u < 0) {
    u += md;
  }
  return u;
}

namespace ntt {
int base = 1, root = -1, max_base = -1;
vector<int> rev = {0, 1}, roots = {0, 1};

void init() {
int temp = md - 1;
max_base = 0;
while (temp % 2 == 0) {
temp >>= 1;
++max_base;
}
root = 2;
while (true) {
if (power(root, 1 << max_base) == 1 && power(root, 1 << max_base - 1) != 1) {
      break;
    }
    ++root;
  }
}

void ensure_base(int nbase) {
  if (max_base == -1) {
    init();
  }
  if (nbase <= base) {
    return;
  }
  assert(nbase <= max_base);
  rev.resize(1 << nbase);
  for (int i = 0; i < 1 << nbase; ++i) {
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << nbase - 1;
  }
  roots.resize(1 << nbase);
  while (base < nbase) {
    int z = power(root, 1 << max_base - 1 - base);
    for (int i = 1 << base - 1; i < 1 << base; ++i) {
      roots[i << 1] = roots[i];
      roots[i << 1 | 1] = mul(roots[i], z);
    }
    ++base;
  }
}

void dft(vector<int> &a) {
int n = a.size(), zeros = __builtin_ctz(n);
ensure_base(zeros);
int shift = base - zeros;
for (int i = 0; i < n; ++i) {
    if (i < rev[i] >> shift) {
swap(a[i], a[rev[i] >> shift]);
}
}
for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j += i << 1) {
      for (int k = 0; k < i; ++k) {
        int x = a[j + k], y = mul(a[j + k + i], roots[i + k]);
        a[j + k] = (x + y) % md;
        a[j + k + i] = (x + md - y) % md;
      }
    }
  }
}

vector<int> multiply(vector<int> a, vector<int> b) {
int need = a.size() + b.size() - 1, nbase = 0;
while (1 << nbase < need) {
    ++nbase;
  }
  ensure_base(nbase);
  int sz = 1 << nbase;
  a.resize(sz);
  b.resize(sz);
  bool equal = a == b;
  dft(a);
  if (equal) {
    b = a;
  } else {
    dft(b);
  }
  int inv_sz = inv(sz);
  for (int i = 0; i < sz; ++i) {
    a[i] = mul(mul(a[i], b[i]), inv_sz);
  }
  reverse(a.begin() + 1, a.end());
  dft(a);
  a.resize(need);
  return a;
}

vector<int> inverse(vector<int> a) {
int n = a.size(), m = n + 1 >> 1;
if (n == 1) {
return vector<int>(1, inv(a[0]));
} else {
vector<int> b = inverse(vector<int>(a.begin(), a.begin() + m));
int need = n << 1, nbase = 0;
    while (1 << nbase < need) {
      ++nbase;
    }
    ensure_base(nbase);
    int sz = 1 << nbase;
    a.resize(sz);
    b.resize(sz);
    dft(a);
    dft(b);
    int inv_sz = inv(sz);
    for (int i = 0; i < sz; ++i) {
      a[i] = mul(mul(md + 2 - mul(a[i], b[i]), b[i]), inv_sz);
    }
    reverse(a.begin() + 1, a.end());
    dft(a);
    a.resize(n);
    return a;
  }
}
}

using ntt::multiply;
using ntt::inverse;

vector<int>& operator += (vector<int> &a, const vector<int> &b) {
if (a.size() < b.size()) {
    a.resize(b.size());
  }
  for (int i = 0; i < b.size(); ++i) {
    add(a[i], b[i]);
  }
  return a;
}

vector<int> operator + (const vector<int> &a, const vector<int> &b) {
vector<int> c = a;
return c += b;
}

vector<int>& operator -= (vector<int> &a, const vector<int> &b) {
if (a.size() < b.size()) {
    a.resize(b.size());
  }
  for (int i = 0; i < b.size(); ++i) {
    sub(a[i], b[i]);
  }
  return a;
}

vector<int> operator - (const vector<int> &a, const vector<int> &b) {
vector<int> c = a;
return c -= b;
}

vector<int>& operator *= (vector<int> &a, const vector<int> &b) {
if (min(a.size(), b.size()) < 128) {
    vector<int> c = a;
a.assign(a.size() + b.size() - 1, 0);
for (int i = 0; i < c.size(); ++i) {
      for (int j = 0; j < b.size(); ++j) {
        add(a[i + j], mul(c[i], b[j]));
      }
    }
  } else {
    a = multiply(a, b);
  }
  return a;
}

vector<int> operator * (const vector<int> &a, const vector<int> &b) {
vector<int> c = a;
return c *= b;
}

vector<int>& operator /= (vector<int> &a, const vector<int> &b) {
int n = a.size(), m = b.size();
if (n < m) {
    a.clear();
  } else {
    vector<int> c = b;
reverse(a.begin(), a.end());
reverse(c.begin(), c.end());
c.resize(n - m + 1);
a *= inverse(c);
a.erase(a.begin() + n - m + 1, a.end());
reverse(a.begin(), a.end());
}
return a;
}

vector<int> operator / (const vector<int> &a, const vector<int> &b) {
vector<int> c = a;
return c /= b;
}

vector<int>& operator %= (vector<int> &a, const vector<int> &b) {
int n = a.size(), m = b.size();
if (n >= m) {
vector<int> c = (a / b) * b;
a.resize(m - 1);
for (int i = 0; i < m - 1; ++i) {
      sub(a[i], c[i]);
    }
  }
  return a;
}

vector<int> operator % (const vector<int> &a, const vector<int> &b) {
vector<int> c = a;
return c %= b;
}

vector<int> derivative(const vector<int> &a) {
int n = a.size();
vector<int> b(n - 1);
for (int i = 1; i < n; ++i) {
    b[i - 1] = mul(a[i], i);
  }
  return b;
}

vector<int> primitive(const vector<int> &a) {
int n = a.size();
vector<int> b(n + 1), invs(n + 1);
for (int i = 1; i <= n; ++i) {
    invs[i] = i == 1 ? 1 : mul(md - md / i, invs[md % i]);
    b[i] = mul(a[i - 1], invs[i]);
  }
  return b;
}

vector<int> logarithm(const vector<int> &a) {
vector<int> b = primitive(derivative(a) * inverse(a));
b.resize(a.size());
return b;
}

vector<int> exponent(const vector<int> &a) {
vector<int> b(1, 1);
while (b.size() < a.size()) {
    vector<int> c(a.begin(), a.begin() + min(a.size(), b.size() << 1));
    add(c[0], 1);
    vector<int> old_b = b;
b.resize(b.size() << 1);
    c -= logarithm(b);
    c *= old_b;
    for (int i = b.size() >> 1; i < b.size(); ++i) {
      b[i] = c[i];
    }
  }
  b.resize(a.size());
  return b;
}

vector<int> power(const vector<int> &a, int m) {
int n = a.size(), p = -1;
vector<int> b(n);
for (int i = 0; i < n; ++i) {
    if (a[i]) {
      p = i;
      break;
    }
  }
  if (p == -1) {
    b[0] = !m;
    return b;
  }
  if ((long long) m * p >= n) {
return b;
}
int mu = power(a[p], m), di = inv(a[p]);
vector<int> c(n - m * p);
for (int i = 0; i < n - m * p; ++i) {
    c[i] = mul(a[i + p], di);
  }
  c = logarithm(c);
  for (int i = 0; i < n - m * p; ++i) {
    c[i] = mul(c[i], m);
  }
  c = exponent(c);
  for (int i = 0; i < n - m * p; ++i) {
    b[i + m * p] = mul(c[i], mu);
  }
  return b;
}

vector<int> sqrt(const vector<int> &a) {
vector<int> b(1, 1);
while (b.size() < a.size()) {
    vector<int> c(a.begin(), a.begin() + min(a.size(), b.size() << 1));
    vector<int> old_b = b;
b.resize(b.size() << 1);
    c *= inverse(b);
    for (int i = b.size() >> 1; i < b.size(); ++i) {
      b[i] = mul(c[i], md + 1 >> 1);
}
}
b.resize(a.size());
return b;
}

vector<int> multiply_all(int l, int r, vector<vector<int>> &all) {
if (l > r) {
return vector<int>();
} else if (l == r) {
return all[l];
} else {
int y = l + r >> 1;
return multiply_all(l, y, all) * multiply_all(y + 1, r, all);
}
}

vector<int> evaluate(const vector<int> &f, const vector<int> &x) {
int n = x.size();
if (!n) {
return vector<int>();
}
vector<vector<int>> up(n * 2);
for (int i = 0; i < n; ++i) {
    up[i + n] = vector<int>{(md - x[i]) % md, 1};
}
for (int i = n - 1; i; --i) {
up[i] = up[i << 1] * up[i << 1 | 1];
  }
  vector<vector<int>> down(n * 2);
down[1] = f % up[1];
for (int i = 2; i < n * 2; ++i) {
    down[i] = down[i >> 1] % up[i];
}
vector<int> y(n);
for (int i = 0; i < n; ++i) {
    y[i] = down[i + n][0];
  }
  return y;
}

vector<int> interpolate(const vector<int> &x, const vector<int> &y) {
int n = x.size();
vector<vector<int>> up(n * 2);
for (int i = 0; i < n; ++i) {
    up[i + n] = vector<int>{(md - x[i]) % md, 1};
}
for (int i = n - 1; i; --i) {
up[i] = up[i << 1] * up[i << 1 | 1];
  }
  vector<int> a = evaluate(derivative(up[1]), x);
for (int i = 0; i < n; ++i) {
    a[i] = mul(y[i], inv(a[i]));
  }
  vector<vector<int>> down(n * 2);
for (int i = 0; i < n; ++i) {
    down[i + n] = vector<int>(1, a[i]);
}
for (int i = n - 1; i; --i) {
down[i] = down[i << 1] * up[i << 1 | 1] + down[i << 1 | 1] * up[i << 1];
  }
  return down[1];
}

const int N=201000;
ll val[1010],c[5][N],d[5][N],ss[N];
int q,p[1010];
char s[N],t[N];

int main() {
	rep(i,0,26) val[i]=rnd(mod);
	rep(i,0,26) {
		int q;
		scanf("%d",&q);
		p[q-1]=i;
	}
	scanf("%s",t);
	scanf("%s",s);
	int n=strlen(s);
	rep(i,0,n) {
		int id=s[i]-'a';
		ll u=val[id],v=val[p[id]];
		c[4][i]=1;
		c[3][i]=(-2*u-2*v)%mod;
		c[2][i]=(u*u+4*u*v+v*v)%mod;
		c[1][i]=-2*u*v%mod*(u+v)%mod;
		c[0][i]=u*u%mod*v%mod*v%mod;
	}
	rep(i,0,n) rep(j,0,5) if (c[j][i]<0) c[j][i]+=mod;
	int m=strlen(t);
	rep(i,0,m) {
		ll u=val[t[i]-'a'];
		d[0][i]=1;
		rep(x,1,5) d[x][i]=d[x-1][i]*u%mod;
	}
	rep(x,0,5) {
		reverse(d[x],d[x]+m);
		auto a=multiply(VI(d[x],d[x]+m),VI(c[x],c[x]+n));
		rep(j,m-1,n) ss[j]=(ss[j]+a[j])%mod;
	}
	rep(j,m-1,n) putchar(ss[j]==0?'1':'0');
	puts("");
}

Arson In Berland Forest

Finding the Eulerian path in $O(M)$

Design Tutorial: Learn from a Game

Parity

Remove Duplicates

Dima and Figure