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. 		if(a[j]==a[i]) {
  11. 			ind[i]=j++;
  12. 		} else {
  13. 			while(j>0) {
  14. 				j=ind[j-1];
  15. 				if(a[j]==a[i])  {
  16. 					ind[i]=j++;
  17. 					break;
  18. 				}
  19. 			}
  20. 		}
  21. 		cout<<i<<" "<<ind[i]<<endl;
  22. 	}
  23. 	return ;
  24. }
  25.  
  26. int findAinB(char *b, char *a, int *indTable, int n, int m) {
  27. 	int j = 0;
  28. 	for(int i = 0 ; i < m ; i++) {
  29. 		if(a[j]==b[i]) {
  30. 			j++;
  31. 			i++;
  32. 			if(j==n) { return i-n+1; }
  33. 		} else {
  34. 			if(j>0) { j=indTable[j-1]; }
  35. 		}
  36. 	}
  37. 	return -1;
  38. }
  39.  
  40. int main() {
  41. 	char a[256];
  42. 	scanf("%s",a);
  43. 	int len = strlen(a);
  44. 	int indTable[len];
  45. 	calculate(indTable, a, len);
  46. 	char b[256];
  47. 	cin>>b;
  48. 	cout<<findAinB(b, a, indTable, len, strlen(b))<<endl;
  49.  
  50. 	return 0;
  51. }
Success #stdin #stdout 0.01s 2728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 -1218046944
2 134516226
3 -1076875292
4 0
5 -1218048012
6 -1076874472
7 134515603
8 134516226
9 -1076874744
10 -1216679996
11 -1076875204
-1
https://ideone.com/d4Jfr
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!