[ LightOJ ] 1255- Substring Frequency

Author            : Anwar Jahid Ruman Hossain 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [ LightOJ ] 1255- Substring Frequency
Source            : URI Online Judge
Category          : Pattern Searching
Algorithm         : Z-algorithm
Verdict           : Accepted

1. /*__//\\//\\//\\//\\//\\= BISMILLAHIR RAHMANIR RAHIM =//\\//\\//\\//\\//\\//__*/  
2. #include <bits/stdc++.h>  
3. //........................</HEADER>................................  
4. #include <ext/pb_ds/assoc_container.hpp> // Common file  
5. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update  
6. #include <ext/pb_ds/detail/standard_policies.hpp>  
7.   
8. using namespace std;  
9. //........................</CONSTANT DEFINE>........................  
10. const unsigned int MOD = 1000000007;  
11. #define ll long long  
12.   
13. #define Imax 1e9+5  
14. #define LLmax 1e18  
15.   
16. #define Imin -1e9-5  
17. #define LLmin -1e18  
18.   
19. #define PI acos(-1.0)  
20. #define EPS 1e-9  
21. #define INF 1<<28  
22.   
23. //........................</LOOP >.................................  
24. #define rep(i,a,n) for(int i=a;i<n;i++)  
25. #define per(i,a,n) for(int i=n-1;i>=a;i--)  
26.   
27. //................</ STANDARTD TEMPLATE LIBRARY>...................  
28. #define all(x) (x).begin(),(x).end()  
29. #define pb(x) push_back(x)  
30. #define mp(a,b) make_pair((a),(b))  
31.   
32. //........................</ TYPE CONVERSION>......................  
33. #define toRad(a) ((a)*(PI)/180)  
34. #define toDeg(a) ((a)*180/(PI))  
35.   
36. //........................</ MATH>.................................  
37. #define max3(a,b,c) max(a,max(b,c))  
38. #define min3(a,b,c) min(a,min(b,c))  
39. #define sq(a) ((a)*(a))  
40. inline bool isEq(double a,double b){  
41.     return (abs(a-b)<EPS);  
42. }  
43. template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}  
44. template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}  
45.   
46. //........................</ ARRAY DEFAULT>........................  
47. #define mem(a,v) memset(a,v,sizeof(a))  
48. string day [] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};  
49. int month[]={31,28,31,30,31,30,31,31,30,31,30,31};  //Not Leap Year  
50.   
51. //........................</DIRECTION>.............................  
52. int dx4[]={1,0,-1,0};  
53. int dy4[]={0,1,0,-1}; //4 Direction  
54.   
55. int dx8[]={1,1,0,-1,-1,-1,0,1};  
56. int dy8[]={0,1,1,1,0,-1,-1,-1};//8 direction  
57.   
58. int dxh[]={2,1,-1,-2,-2,-1,1,2};  
59. int dyh[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction (horse)  
60.   
61. //........................</ INPUT/OUTPUT>.........................  
62. #define read(n) scanf("%d",&n)  
63. #define write(n) printf("%d",n)  
64. #define endl '\n'  
65.   
66. #define PRECISION(x) cout << fixed << setprecision(x)  
67. #define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
68.   
69. //.......................</ PRE DEFINED FUNCTIONS>..................  
70. bool sortByFirst(const pair<int,int>&a,const pair<int,int>&b){  
71.     return a.first>b.first;  
72. }  
73. //vector <string> v;  
74. //void dfs (string str, string t = "", int cnt = 0) {  
75. //    if (cnt == 2) {  
76. //        v.push_back (t);  
77. //        return;  
78. //    } else {  
79. //        for (int i = 0; i <(int)str.size (); i ++) {  
80. //            dfs (str, t + str [i], cnt + 1);  
81. //        }  
82. //    }  
83. //}  
84. //vector<vector<int> >divisor(100005);  
85. //void divisors(){  
86. //    for(int i=1;i<100005;i++){  
87. //        for(int j=i;j<100005;j+=i){  
88. //           divisor[j].push_back(i);  
89. //        }  
90. //    }  
91. //}  
92. void getZarray(string str, int z[]){  
93.     int n=str.length();  
94.     int left,right,k;  
95.     left=right=0;  
96.     for(int i=1;i<n;i++){  
97.         if(i>right){  
98.             left=right=i;  
99.             while(right<n && str[right-left]==str[right]){  
100.                 right++;  
101.             }  
102.             z[i]=right-left;  
103.             right--;  
104.         }else{  
105.             k=i-left;  
106.             if(z[k]<right-i+1){  
107.                 z[i]=z[k];  
108.             }else{  
109.                 left=i;  
110.                 while(right<n && str[right-left]==str[right]){  
111.                     right++;  
112.                 }  
113.                 z[i]=right-left;  
114.                 right--;  
115.             }  
116.         }  
117.     }  
118. }  
119. int period_count(string text,string pattern){  
120.     string concat=pattern+"$"+text;  
121.     int cnt=0;  
122.     int len=concat.length();  
123.     int z[len];  
124.     getZarray(concat,z);  
125.     int flag=0;  
126.     for(int i=1;i<len;i++){  
127.         if(z[i]==pattern.length()){  
128.             cnt++;  
129.         }  
130.     }  
131.     return cnt;  
132. }  
133. int main () {  
134.     FAST_IO  
135. //    freopen("input.txt","r",stdin);  
136. //    freopen("output.txt","w",stdout);  
137.   
138.     int t;  
139.     cin>>t;  
140.     for(int i=1;i<=t;i++){  
141.         string text,pattern;  
142.         cin>>text>>pattern;  
143.         cout<<"Case "<<i<<": "<<period_count(text,pattern)<<endl;  
144.     }  
145.     return 0;  
146. }