FilesExpand file tree

 master

/

3461.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

93 lines (81 loc) · 1.58 KB

 master

/

3461.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

93 lines (81 loc) · 1.58 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

#include <iostream>

#include <string>

using namespace std;

const int MAXN = 50000;

//char P[MAXN], Text[MAXN];

string P,Text;

int failure[MAXN];

int T;

void build_failure(){

failure[0] =0;

failure[1] = 0;

unsigned sz = P.length();

int j;

for(int i=2; i<=sz; i++){

/*

if(i<0 || i>sz){

cout<<"ERROR: "<<i<<endl;

}

*/

j = failure[i-1];

for(;;){

if(P[i-1]==P[j]){

failure[i] = j+1;

break;

}

if(j==0){

failure[i] = 0;

break;

}

j = failure[j];

}

}

/*

for(int i=0; i<=sz; i++){

cout<<failure[i]<<" ";

}cout<<endl;

*/

}

void work(){

build_failure();

//int text_sz = strlen(Text);

//int p_sz = strlen(P);

unsigned text_sz = Text.length();

unsigned p_sz = P.length();

int i,j=0;

int ans = 0;

for(;;){

/*

if(i<0 || j<0 || i>p_sz || j>text_sz){

cout<<"ERROR: "<<i<<" "<<j<<endl;

}

*/

if(j>=text_sz)break;

if(Text[j]==P[i]){

i++;

j++;

if(i>=p_sz){

i=failure[p_sz];

ans++;

continue;

}

}else if(i>0){

i = failure[i];

}else{

j++;

}

}

cout<<ans<<endl;

}

int main(){

cin>>T;

//scanf("%d",&T);

while(T--){

//scanf("%s",P);

//scanf("%s",Text);

cin>>P;

cin>>Text;

work();

}

return 0;

}