fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <algorithm>
  6. using namespace std;
  7. #define re(i, n) for (int i=0; i<n; i++)
  8. #define re1(i, n) for (int i=1; i<=n; i++)
  9. #define re2(i, l, r) for (int i=l; i<r; i++)
  10. #define re3(i, l, r) for (int i=l; i<=r; i++)
  11. #define rre(i, n) for (int i=n-1; i>=0; i--)
  12. #define rre1(i, n) for (int i=n; i>0; i--)
  13. #define rre2(i, r, l) for (int i=r-1; i>=l; i--)
  14. #define rre3(i, r, l) for (int i=r; i>=l; i--)
  15. #define ll long long
  16. #define root 1
  17. const int MAXN = 300010, MAXS = 4000000, INF = ~0U >> 2;
  18. struct node {
  19. 	bool FF;
  20. 	int KK, fail, ch[26];
  21. } T[MAXS];
  22. struct sss {
  23. 	int l, r;
  24. 	bool operator< (sss s0) const {return l < s0.l || l == s0.l && r < s0.r;}
  25. } A[MAXN];
  26. int n, S, Q[MAXS], res = 0;
  27. char ss[MAXN], ss0[MAXN];
  28. void ins()
  29. {
  30. 	int len = strlen(ss0), x = root, c;
  31. 	re(i, len) {
  32. 		c = ss0[i] - 97;
  33. 		if (!T[x].ch[c]) {T[x].ch[c] = ++S;}
  34. 		x = T[x].ch[c];
  35. 	}
  36. 	T[x].FF = 1; T[x].KK = len;
  37. }
  38. void init()
  39. {
  40. 	scanf("%d%s", &n, ss); S = 1;
  41. 	int m0; scanf("%d", &m0);
  42. 	re(i, m0) {
  43. 		scanf("%s", ss0); ins();
  44. 	}
  45. }
  46. void prepare()
  47. {
  48. 	Q[0] = root; T[root].fail = 0; int i, j, x;
  49. 	for (int front=0, rear=0; front<=rear; front++) {
  50. 		i = Q[front];
  51. 		re(k, 26) if (j = T[i].ch[k]) {
  52. 			x = T[i].fail;
  53. 			while (x && !T[x].ch[k]) x = T[x].fail;
  54. 			if (T[x].ch[k]) x = T[x].ch[k]; else x = root;
  55. 			T[j].fail = x; if (T[x].FF && !T[j].FF) {T[j].FF = 1; T[j].KK = T[x].KK;}
  56. 			Q[++rear] = j;
  57. 		}
  58. 	}
  59. }
  60. void solve()
  61. {
  62. 	int x = root, c, n0 = 0;
  63. 	re(i, n) {
  64. 		c = ss[i] - 97;
  65. 		while (x && !T[x].ch[c]) x = T[x].fail;
  66. 		if (T[x].ch[c]) x = T[x].ch[c]; else x = root;
  67. 		if (T[x].FF) {A[n0].l = i - T[x].KK + 1; A[n0++].r = i;}
  68. 	}
  69. 	sort(A, A + n0); int maxr;
  70. 	if (n0) {
  71. 		if (A[0].l) res = A[0].l; maxr = A[0].r;
  72. 		re2(i, 1, n0) {
  73. 			if (A[i].l > maxr + 1) res += A[i].l - maxr - 1;
  74. 			if (A[i].r > maxr) maxr = A[i].r;
  75. 		}
  76. 		if (maxr < n - 1) res += n - maxr - 1;
  77. 	} else res = n;
  78. }
  79. void pri()
  80. {
  81. 	printf("%d\n", res);
  82. }
  83. int main()
  84. {
  85. 	init();
  86. 	prepare();
  87. 	solve();
  88. 	pri();
  89. 	return 0;
  90. }
  91.  
Runtime error #stdin #stdout 0.01s 148KB
comments (?)
stdin
copy 
6
abcabc
2
abca
cab
stdout
copy 
Standard output is empty
https://ideone.com/aWQ8O
language:
C++ (gcc 8.3)
created:
12 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!