#include <bits/stdc++.h>
using namespace std;
const int MAXN = (1 << 18);
const int MAXK = 10;
int n, m, k;
string s;
int st[2 * MAXN][MAXK][MAXK];
int fir[2 * MAXN], las[2 * MAXN];
int lazy[2 * MAXN];
void build(int node, int low, int high) {
  memset(st[node], 0, sizeof(node));
  lazy[node] = -1;
  if (low == high) {
    fir[node] = s[low] - 'a';
    las[node] = s[low] - 'a';
    return;
  }
  build(2 * node + 1, low, (low + high) / 2);
  build(2 * node + 2, (low + high) / 2 + 1, high);
  for (int i = 0; i < k; i++) {
    for (int j = 0; j < k; j++) {
      st[node][i][j] = st[2 * node + 1][i][j] + st[2 * node + 2][i][j];
    }
  }
  st[node][las[2 * node + 1]][fir[2 * node + 2]]++;
  fir[node] = fir[2 * node + 1];
  las[node] = las[2 * node + 2];
}
void upgrade(int node, int low, int high) {
  if (lazy[node] != -1) {
    int v = lazy[node];
    memset(st[node], 0, sizeof(st[node]));
    st[node][v][v] = high - low;
    fir[node] = v;
    las[node] = v;
    if (low != high) {
      lazy[2 * node + 1] = lazy[node];
      lazy[2 * node + 2] = lazy[node];
    }
    lazy[node] = -1;
  }
}
void update(int node, int low, int high, int qx, int qy, int val) {
  upgrade(node, low, high);
  if (qx > high || qy < low) return;
  if (qx <= low && high <= qy) {
    lazy[node] = val;
    upgrade(node, low, high);
    return;
  }
  update(2 * node + 1, low, (low + high) / 2, qx, qy, val);
  update(2 * node + 2, (low + high) / 2 + 1, high, qx, qy, val);
  memset(st[node], 0, sizeof(st[node]));
  for (int i = 0; i < k; i++) {
    for (int j = 0; j < k; j++) {
      st[node][i][j] = st[2 * node + 1][i][j] + st[2 * node + 2][i][j];
    }
  }
  st[node][las[2 * node + 1]][fir[2 * node + 2]]++;
  fir[node] = fir[2 * node + 1];
  las[node] = las[2 * node + 2];
}
int query(string p) {
  int ans = 1;
  for (int i = 0; i < k; i++) {
    for (int j = 0; j <= i; j++) {
      ans += st[0][p[i] - 'a'][p[j] - 'a'];
    }
  }
  return ans;
}
int main(void) {
  cin >> n >> m >> k >> s;
  build(0, 0, n - 1);
  for (int i = 0; i < m; i++) {
    int op;
    cin >> op;
    if (op == 1) {
      int l, r;
      char c;
      cin >> l >> r >> c;
      update(0, 0, n - 1, l - 1, r - 1, c - 'a');
    } else {
      cin >> s;
      cout << query(s) << "\n";
    }
  }
  return 0;
}
