fork download
copy 
  1. #include <bits/stdc++.h> 
  2. #define N 10000000
  3. using namespace std;
  4. vector<int> z(N);
  5.  
  6. int n;
  7. char s;
  8.  
  9. void zfun(string s){
  10. 	int len = s.length();
  11. 	int l =0;
  12. 	int r =0;
  13. 	for(int i=1;i<len;i++){
  14. 		if(i<=r)
  15. 			z[i] = min(r-i+1,z[i-l]);
  16. 		while(i+z[i]<len && s[z[i]] == s[i+z[i]]){
  17. 			z[i]++;
  18. 		}
  19. 		if(z[i] > r-l+1){
  20. 			l = i;
  21. 			r = i + z[i] - 1;
  22. 		}
  23. 	}
  24. }
  25.  
  26.  
  27. void printanswer(string s){
  28. 	int len  = s.length();
  29. 	for(int i =n+1;i<len;i++){
  30. 		if(z[i] == n){
  31. 			cout<<i-n-1<<endl;
  32. 		}
  33. 	}
  34. }
  35. int main()
  36. {
  37.  
  38. while(1)
  39. {
  40. 	if(scanf("%c",&s) == EOF)	break;
  41. 	z.clear();
  42. 	z.resize(N);
  43. 	n = s - '0';
  44. 	string a,b;
  45. 	cin>>a>>b;
  46. 	string c = a+(char)254+b;
  47. 	zfun(c);
  48. 	printanswer(c);
  49. 	cout<<"\n\n";
  50. 	if(getchar() == EOF)	return 0;;
  51. }
  52. return 0;
  53. }
Success #stdin #stdout 0.1s 3468KB
comments (?)
stdin
copy 
2
na
banananobano
3
foo
foobar
9
foobarfoo
barfoobarfoobarfoobarfoobarfoo
stdout
copy 
2
4


0


3
9
15
21
https://ideone.com/Jf8k26
language:
C++14 (gcc 8.3)
created:
9 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!