fork download
  1. //bài này có sử dụng kiến thức về trie, em có thể đọc thêm tại đây nhé: bom.so/J2Zln5
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define int long long
  5. const int mxn = 25 * (int)1e6, inf = 1e18,mxc = 5005;
  6. map<int,int> mp[26],depth,dem;
  7. int cnt,ans,n,m;
  8. char c[mxc][mxc];
  9. string srr[mxc];
  10. int ins(string &s)
  11. {
  12. int u = 0;
  13. for(auto c : s)
  14. {
  15. int id = c - 'a';
  16. if(!mp[id][u])
  17. {
  18. mp[id][u] = ++cnt;
  19. }
  20. depth[mp[id][u]] = depth[u] + 1;
  21. u = mp[id][u];
  22. dem[u]++;
  23. if(dem[u] > 1) ans = max(ans, depth[u]);
  24. //cout << ans << '\n';
  25. }
  26. return u;
  27. }
  28. int32_t main()
  29. {
  30. cin.tie(0)->sync_with_stdio(0);
  31. cin >> n >> m;
  32. for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> c[i][j];
  33. for(int j = 0; j < m ; j++)
  34. {
  35. for(int i = n - 1; i >= 0; i--) srr[j] += c[i][j];
  36. ins(srr[j]);
  37. }
  38. cout << n - ans - 1 << '\n';
  39. return 0;
  40. }
  41.  
Success #stdin #stdout 0s 5308KB
stdin
Standard input is empty
stdout
-1