fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. using namespace std;
  6. const int MAX = 1e4+5;
  7. int f[MAX];
  8. int l;
  9. char p[MAX];
  10. void init()
  11. {
  12. 	for(int i=0;i<=l;i++)f[i]=0;
  13. }
  14. void failure_function()
  15. {
  16. 	//int l = strlen(p);
  17. 	init();
  18. 	int j=0;
  19. 	for(int i=1;i<l;i++)
  20. 	{
  21. 		while(j>=0&&p[j]!=p[i])
  22. 		{
  23. 			if(j-1>=0)
  24. 				j = f[j-1];
  25. 			else
  26. 				j = -1;
  27. 		}
  28. 		j += 1;
  29. 		f[i] = j;
  30. 	}
  31.  
  32. }
  33. void find_occurrences()
  34. {
  35. 	failure_function();
  36. 	int flag=1;
  37. 	int lp = l;
  38. 	char c=getchar();
  39. 	int j=0,i=0;
  40. 	while((c = getchar())!='\n')
  41. 	{
  42. 		if(c==EOF)
  43. 		exit(0);
  44. 		while(j>=0&&c!=p[j])
  45. 		{
  46. 			if(j-1>=0)
  47. 				j = f[j-1];
  48. 			else
  49. 				j = -1;
  50. 		}
  51. 		j+=1;
  52. 		if(j==lp)
  53. 		{
  54. 			flag=0;
  55. 			j = f[lp-1];
  56. 			printf("%d\n",i-lp+1);
  57. 		}
  58. 		i++;
  59. 	}
  60. 	if(flag)
  61. 	printf("\n");
  62.  
  63.  
  64. }
  65. int main(void)
  66. {
  67. 	while(1)
  68. 	{
  69. 	scanf("%d",&l);
  70. 	scanf("%s",p);
  71.  
  72. 	find_occurrences();
  73. 	}
  74. }
Success #stdin #stdout 0s 3512KB
comments (?)
stdin
copy 
2
na
banananobano
6
foobar
foo
9
foobarfoo
barfoobarfoobarfoobarfoobarfoo
stdout
copy 
2
4

3
9
15
21
https://ideone.com/Y5JwLD
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!