C-plus-codes/p137.cpp at main · Rishsach/C-plus-codes

History

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

#include<iostream>

using namespace std;

void getZarr(string str, int Z[]);

void search(string text, string pattern)

{

string concat = pattern + "$" + text;

int l = concat.length();

int Z[l];

getZarr(concat, Z);

for (int i = 0; i < l; ++i)

{

if (Z[i] == pattern.length())

cout << "Pattern found at index "

<< i - pattern.length() -1 << endl;

}

void getZarr(string str, int Z[])

{

int n = str.length();

int L, R, k;

L = R = 0;

for (int i = 1; i < n; ++i)

{

if (i > R)

{

L = R = i;

while (R<n && str[R-L] == str[R])

R++;

Z[i] = R-L;

R--;

}

else

{

k = i-L;

if (Z[k] < R-i+1)

Z[i] = Z[k];

else

{

L = i;

while (R<n && str[R-L] == str[R])

R++;

Z[i] = R-L;

R--;

}

int main()

{

string text = "RISHABH";

string pattern = "RISH";

search(text, pattern);

return 0;

}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

p137.cpp

p137.cpp

Files

p137.cpp

Latest commit

History

p137.cpp

File metadata and controls