code_heavy

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
typedef pair<ULL, int> ii;

const int N = 5004;
int n, k, numMap;
string str;

ULL Hash[N], Pow[N];
ULL getHash(int i, int j) { return Hash[j] - Hash[i-1] * Pow[j-i+1]; }

int num[3];
map<ii, int> Map;
vector<int> adj[N];

int getMap(int l, int r, int type) {
    ULL tmp = getHash(l, r);
    if (!Map[ii(tmp, type)]) Map[ii(tmp, type)] = ++num[type];
    return Map[ii(tmp, type)];
}

void Build_Edge() {
    int len = str.length(); str = " " + str;
    for (int i = 1; i <= len; ++i) Hash[i] = Hash[i-1] * 31LL + str[i] - 'a' + 1;

    adj[getMap(1, k, 0)].push_back(getMap(len-k+1, len, 1));
}

int vis[N], Match[N], Assign[N], Time;

bool DFS(int u) {
    if (vis[u] == Time) return false; vis[u] = Time;
    for (int v : adj[u])
        if (!Assign[v] || DFS(Assign[v])) {
            Assign[v] = u; Match[u] = v;
            return true;
        }
    return false;
}

void sol() {
    int res = 0;
    while (true) {
        bool End = true; ++Time;
        for (int i = 1; i <= num[0]; ++i) {
            if (Match[i] || vis[i] == Time || !DFS(i)) continue;
            End = false; res++;
        }
        if (End) break;
    }
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("input.txt", "r")) {
        freopen("input.txt", "r", stdin);
    }
    else if (fopen("heavy.inp", "r")) {
        freopen("heavy.inp", "r", stdin);
        freopen("heavy.out", "w", stdout);
    }

    cin >> n >> k;
    for (int i = 0; i <= n; ++i) Pow[i] = (i == 0) ? 1 : Pow[i-1] * 31LL;

    for (int i = 1; i <= n; ++i) {
        cin >> str;
        Build_Edge();
    }

    sol();

    return 0;
}