fork download
copy 
  1. #include<iostream>
  2. #include<string.h>
  3. using namespace std;
  4.  
  5. void calculate(int *ind, char *a, int len) {
  6. 	if(len==0) return ;
  7. 	ind[0]=0;
  8. 	int j = 0 ;
  9. 	for(int i = 1; i < len ; i++ ) {
  10. 		cout<<i<<" "<<ind[i]<<" "<<j<<endl;
  11. 		ind[i]=0;
  12. 		if(a[j]==a[i]) {
  13. 			ind[i]=j++;
  14. 		} else {
  15. 			while(j>0) {
  16. 				j=ind[j-1];
  17. 				if(a[j]==a[i])  {
  18. 					ind[i]=j++;
  19. 					break;
  20. 				}
  21. 			}
  22. 		}
  23. 		cout<<i<<" "<<ind[i]<<" "<<j<<endl;
  24. 	}
  25. 	return ;
  26. }
  27.  
  28. int findAinB(char *b, char *a, int *indTable, int n, int m) {
  29. 	int j = 0;
  30. 	for(int i = 0 ; i < m ; i++) {
  31. 		if(a[j]==b[i]) {
  32. 			j++;
  33. 			i++;
  34. 			if(j==n) { return i-n+1; }
  35. 		} else {
  36. 			if(j>0) { j=indTable[j-1]; }
  37. 		}
  38. 	}
  39. 	return -1;
  40. }
  41.  
  42. int main() {
  43. 	char a[256];
  44. 	scanf("%s",a);
  45. 	int len = strlen(a);
  46. 	int indTable[len];
  47. 	calculate(indTable, a, len);
  48. 	char b[256];
  49. 	cin>>b;
  50. 	cout<<findAinB(b, a, indTable, len, strlen(b))<<endl;
  51.  
  52. 	return 0;
  53. }
Success #stdin #stdout 0.02s 2728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 -1217137632 0
1 0 0
2 134516514 0
2 0 0
3 -1080606012 0
3 0 0
4 0 0
4 0 0
5 -1217138700 0
5 0 0
6 -1080605192 0
6 0 0
7 134515891 0
7 0 0
8 134516514 0
8 0 0
9 -1080605464 0
9 0 0
10 -1215770684 0
10 0 0
11 -1080605924 0
11 0 0
-1
https://ideone.com/tpNYb
language:
C++ (gcc 8.3)
created:
14 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!