#include #define REP_(i, a_, b_, a, b, ...) for (int i = (a), END_##i = (b); i < END_##i; ++i) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define ALL(x) std::begin(x), std::end(x) using Int = long long; using Uint = unsigned long long; using Real = long double; template inline bool chmax(T &a, U b) { return a < b and ((a = b), true); } template inline bool chmin(T &a, U b) { return a > b and ((a = b), true); } template inline int ssize(const T &a) { return (int) a.size(); } template constexpr T kBigVal = std::numeric_limits::max() / 2; struct CastInput { template operator T() const { T x; std::cin >> x; return x; } struct Sized { int n; template operator T() const { T xs(n); for (auto &x: xs) std::cin >> x; return xs; } }; Sized operator()(int n) const { return {n}; } } in; template std::ostream &print_seq(const Container &seq, const char *sep = " ", const char *ends = "\n", std::ostream &os = std::cout) { const auto itl = std::begin(seq), itr = std::end(seq); for (auto it = itl; it != itr; ++it) { if (it != itl) os << sep; os << *it; } return os << ends; } template inline std::ostream &print_one(const T &x, char endc) { if constexpr (std::is_same::value) { return std::cout << (x ? "Yes" : "No") << endc; } else { return std::cout << x << endc; } } template inline std::ostream &print(const T &x) { return print_one(x, '\n'); } template std::ostream &print(const T &head, Ts... tail) { return print_one(head, ' '), print(tail...); } inline std::ostream &print() { return std::cout << '\n'; } void exit_() { std::cout.flush(), std::cerr.flush(), std::_Exit(0); } #ifdef MY_DEBUG #include "debug_dump.hpp" #include "backward.hpp" backward::SignalHandling kSignalHandling; #else #define DUMP(...) #define cerr if(false)cerr #endif using namespace std; struct RollingHash { using u64 = std::uint64_t; using u128 = __uint128_t; static const u64 kMod = (1ULL << 61) - 1; static u64 base() { static const u64 kBase = []() { std::mt19937_64 engine(std::random_device{}()); std::uniform_int_distribution rand(1000, kMod - 1); return rand(engine); }(); return kBase; } static inline u64 add(u64 a, u64 b) { a += b; return (a >= kMod) ? (a - kMod) : a; } static inline u64 sub(u64 a, u64 b) { return add(a, kMod - b); } static inline u64 mul(u64 a, u64 b) { u128 t = u128(a) * b; u64 na = u64(t >> 61); u64 nb = u64(t & kMod); na += nb; return (na >= kMod) ? (na - kMod) : na; } static u64 pow_base(int i) { static std::vector kPowBase(1, 1); while (int(kPowBase.size()) <= i) { u64 val = mul(kPowBase.back(), base()); kPowBase.push_back(val); } return kPowBase[i]; } // Calculates hash(a || b) from hash(a), hash(b) and length(b). static u64 concat(u64 a_hash, u64 b_hash, int b_length) { return add(mul(a_hash, pow_base(b_length)), b_hash); } }; // Computes hash for any substring in O(1). struct SpanHash : public RollingHash { std::vector cum_hash; // Constructionn: O(n). // All elements must be non-zero. Otherwise we won't be able to distinguish // between [1] and [0, 1]. template explicit SpanHash(const Sequence &s) : cum_hash(s.size() + 1) { int i = 0; for (const auto &x: s) { u64 val = static_cast(x); assert(val != 0); // Ensure all elements are non-zero! cum_hash[i + 1] = add(mul(cum_hash[i], base()), val); ++i; } } // Returns the hash value of the substring s[l:r]. O(1). u64 get(int l, int r) const { // Compute `hash(s[0:r]) - hash(s[0:l]) * B^(r-l) (mod M)` return sub(cum_hash.at(r), mul(cum_hash.at(l), pow_base(r - l))); } }; // Binary search over integers template auto bisect(T truthy, T falsy, F pred) -> T { static_assert(std::is_integral_v); static_assert(std::is_invocable_r_v); while (std::max(truthy, falsy) - std::min(truthy, falsy) > T(1)) { auto mid = (truthy & falsy) + (truthy ^ falsy) / T(2); auto ok = pred(mid); (ok ? truthy : falsy) = std::move(mid); } return truthy; } Int solve() { int n = in, m = in; vector S = in(n); vector SH; for (const auto &s: S) { assert(ssize(s) == m); SH.emplace_back(s); } set < string > candidates; for (int j = 1; j < n; ++j) { for (int i = 0; i <= m; ++i) { if (SH[j].get(0, i) == SH[0].get(0, i)) { candidates.insert(S[j].substr(0, i) + S[0][i] + S[j].substr(i)); } if (SH[j].get(m - i, m) == SH[0].get(m - i, m)) { candidates.insert(S[j].substr(0, m - i) + S[0][m - 1 - i] + S[j].substr(m - i)); } } } DUMP(candidates); int count = 0; for (const string &T: candidates) { SpanHash th(T); bool ok = true; for (int j = 0; j < n; ++j) { int plen = bisect(0, m + 1, [&](int i) { return SH[j].get(0, i) == th.get(0, i); }); int slen = bisect(0, m + 1, [&](int i) { return SH[j].get(m - i, m) == th.get(m + 1 - i, m + 1); }); if (plen + slen >= m) { // ok } else { ok = false; break; } } if (ok) ++count; } return count; } int main() { std::ios::sync_with_stdio(false), cin.tie(nullptr); cout << std::fixed << std::setprecision(18); const int T = 1;//in; REP(t, T) { print(solve()); } exit_(); }