letter

#include <iostream>
#include <fstream>

#include <vector>
#include <string>

#include <algorithm>

#include <cctype>
#include <cassert>

using namespace std;

struct sort_fst {
    const string& s;
    sort_fst(const string& s) : s(s) {}
    bool operator()(int i, int j) { return s[i] < s[j]; }
};

int main() {
    ifstream in("letter.in");
    ofstream out("letter.out");

    int N, M;
    in >> N >> M;

    string a, b;

    for (int i = 0; i < N; ++i) {
        char ch;
        do { in.get(ch); } while (!isalpha(ch));
        a += ch;
    }

    for (int i = 0; i < M; ++i) {
        char ch;
        do { in.get(ch); } while (!isalpha(ch));
        b += ch;
    }

    vector<int> sa(N), sa2(N), rs(N), rk(N), rk2(N);
    for (int i = 0; i < N; ++i) sa[i] = i;
    sort(sa.begin(), sa.end(), sort_fst(a));
    int r = 0;
    for (int i = 1; i < N; ++i) {
        if (a[sa[i]] != a[sa[i-1]])
            rs[++r] = i;
        rk[sa[i]] = r;
    }

    for (int l = 1; l < N; l <<= 1) {
        for (int i = N - l; i < N; ++i)
            sa2[rs[rk[i]]++] = i;
        for (int i = 0; i < N; ++i)
            if (sa[i] >= l)
                sa2[rs[rk[sa[i] - l]]++] = sa[i] - l;
        r = 0;
        rs[sa[0] = sa2[0]] = 0;
        rs[0] = 0;
        for (int i = 1; i < N; ++i) {
            if (rk[sa2[i]] != rk[sa2[i-1]] ||
                sa2[i]+l>=N || sa2[i-1]+l>=N ||
                rk[sa2[i]+l] != rk[sa2[i-1]+l])

                rs[++r] = i;
            rk2[sa[i] = sa2[i]] = r;
        }

        for (int i = 0; i < N; ++i) rk[i] = rk2[i];
    }

    int ans = 1;

    int lo = 0, hi = N, k = 0;
    for (int i = 0; i < M; ++i) {
        int l = lo, h = hi;
        while (l < h) {
            int m = (l + h) / 2;
            if (a[sa[m] + k] < b[i])
                l = m + 1;
            else
                h = m;
        }

        if (l >= hi || a[sa[l] + k] > b[i]) {
            ++ans;
            lo = 0, hi = N, k = 0;
            --i;
            continue;
        }

        lo = l;

        l = lo, h = hi;
        while (l < h) {
            int m = (l + h) / 2;
            if (a[sa[m] + k] <= b[i])
                l = m + 1;
            else
                h = m;
        }
        hi = l;

        ++k;
    }

    out << ans << "\n";

    return 0;
}