fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <queue>
  4. using namespace std;
  5. #define ML 1000005
  6. int N, m;
  7. int a[ML][26], fail[ML], fin[ML], d[ML];
  8. char S[1005];
  9. int main() {
  10. 	while (scanf("%d", &N), N) {
  11. 		m = 0;
  12. 		for (int i = 1; i <= N; i++) {
  13. 			scanf("%s", S + 1);
  14. 			int p = 0;
  15. 			for (int j = 1; S[j]; j++) {
  16. 				if (a[p][S[j] - 'a']) p = a[p][S[j] - 'a'];
  17. 				else ++m, a[p][S[j] - 'a'] = m, p = m;
  18. 			}
  19. 			fin[p]++;
  20. 		}
  21. 		++m;
  22. 		queue <int> q, qf;
  23. 		q.push(0); qf.push(m);
  24. 		int res = 0;
  25. 		while (!q.empty()) {
  26. 			int x = q.front(); q.pop();
  27. 			int xf = qf.front(); qf.pop();
  28. 			fail[x] = xf;
  29. 			if (res < d[x]) res = d[x];
  30. 			for (int i = 0; i < 26; i++) {
  31. 				if (!a[x][i]) continue;
  32. 				int y = a[x][i], yf = xf;
  33. 				if (fin[yf]) fin[x] = 1;
  34. 				while (yf != m && !a[yf][i]) yf = fail[yf];
  35. 				yf = a[yf][i];
  36. 				d[y] = max(d[x], d[yf]) + fin[y];
  37. 				q.push(y);
  38. 				qf.push(yf);
  39. 			}
  40. 		}
  41. 		printf("%d\n", res);
  42. 		for (int i = 0; i <= m; i++) {
  43. 			for (int j = 0; j < 26; j++) a[i][j] = 0;
  44. 			fail[i] = d[i] = fin[i] = 0;
  45. 		}
  46. 	}
  47. }
Success #stdin #stdout 0s 116736KB
comments (?)
stdin
copy 
6
plant
ant
cant
decant
deca
an
2
supercalifragilisticexpialidocious
rag
0
stdout
copy 
4
2
https://ideone.com/mW5Khf
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!