Naive Approach
The naive approach is to check for each substring of size equal to that of the pattern if that is equal to pattern S or not. Therefore, if the size of the string S is s and the pattern P is p, the time complexity of this approach will be O(p*s).
Code in C++
#include<iostream>
#include<string>
using namespace std;
void findPattern(string S,string P){
for(int i=0;i<S.size();i++){
bool flag = true;
for(int j=0;j<P.size();j++){
if(S[i+j]!=P[j]){
flag = false;
break;
}
}
if(flag){
cout<<i<<" ";
}
}
}
int main(){
string S = "abaxabab";
string P = "ba";
cout<<"Pattern "<<P<<" occurs at the indices: ";
findPattern(S,P);
}
Output
Pattern ba occurs at the indices: 1 5
Efficient Approach
We will solve this using the Zalgorithm where time and space complexity is O(s+p) where s = size of the given string and p is the size of the pattern.
Note  We can solve it using KMP with the same time complexity. But since Zalgorithm is easier to understand and implement, we will solve this problem using Zalgorithm in this article. To learn more about the KMP Algorithm, you can go through this article.
ZAlgorithm

In this algorithm, we will be constructing a Zarray.
What is a ZArray?
Z[i] in Zarray will contain the length of the longest substring starting from the index i, which is also the prefix of the string. For example, Letâ€™s construct the Zarray for the string â€śabaxababâ€ť.
The explanation for some indices 

We have Z[4] = 3 because we have a substring of size 3 (â€śabaâ€ť) starting at the 4th index, which is also a prefix of the string (abaxabab).

We have Z[6] = 2 because we have a substring of size 2 (â€śabâ€ť) starting at the 6th index, which is also a prefix of the string (abaxabab).

How is the ZArray constructed for a string S?
We can construct the Zarray in linear time complexity. The main logic is to maintain an interval [L, R] with maximum R such that the substring S[L â€¦ R] is also the prefix of the string S.
Note  Substrings that are prefix too are also known as prefix substrings.
Now, letâ€™s assume we have already computed all the Zvalues till the (i1)th index, and we know the correct interval [L, R] for the index (i1). We will maintain [L, R] and find Z[i] by the following steps:

Case 1: (i>R)
It means no prefixsubstring exists before i that ends at i or after i. So we now compute the new [L, R] by comparing S[0 ..] to S[i..]. Therefore, in this case Z[i] = RL+1.

Case 2: (i<R)
We know S[0â€¦(RL)] matches with S[L...R] where i<R. Therefore, from this, we can also conclude that S[i..R] matches with S[(iL)..(RL)]. Let K = iL. Now there are 2 cases 
 Z[K] < (Ri+1)  It means there is no prefix substring starting at the index i which would extend beyond R. So Z[i] = Z[k].

Z[K] > (Ri+1)  It means we have prefix substring starting at the index i, which can go beyond the index > R. Thus, we need to update [L, R] by updating L=i and match from R+1 onwards.

How is ZArray useful in the searching of patterns?
We will be constructing a Zarray for the string M = Pattern + $ + String. In the Zarray, if the value at any index is equal to the length of the pattern, then we know that we have an occurrence of the pattern starting at the (index  pattern.size()  1) in the original string. For example, letâ€™s construct the Zarray for the string M = â€śbaâ€ť + â€ś$â€ť + â€śabaxababâ€ť where S = â€śabaxababâ€ť and P = â€śbaâ€ť.
Since Z[4] and Z[8] equals 2, the pattern occurs at the (421)th and (821)th index.
Code in C++
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void updateInterval(int& L,int& R,string& M){
while(R<M.size() && M[R]==M[RL]){
R++;
}
R;
}
vector<int> getZArray(string M){
vector<int> zArray(M.size(),0);
int L = 0,R = 0;
for(int i=1;i<M.size();i++){
if(i>R){
L = R = i;
updateInterval(L,R,M);
zArray[i] = RL+1;
}else{
int K = i  L;
if(zArray[K]<(Ri+1)){
zArray[i] = zArray[K];
}else{
L = K;
updateInterval(L,R,M);
zArray[i] = RL+1;
}
}
}
return zArray;
}
void findPattern(string S,string P){
string M = P + "$" + S;
vector<int> zArray = getZArray(M);
for(int i=P.size();i<zArray.size();i++){
if(zArray[i]==P.size()){
// pattern occurs at the current index
cout<<(iP.size()1)<<" ";
}
}
}
int main(){
string S = "abaxabab";
string P = "ba";
cout<<"Pattern "<<P<<" occurs at the indices: ";
findPattern(S,P);
}
Output
Pattern ba occurs at the indices: 1 5
Also check out  Substr C++
Frequently Asked Questions
1.What is the difference between a subsequence and a subarray (or substring in the case of a string)?
A subsequence is formed by deriving 0 or more elements from a sequence without changing the relative order of the elements in the original sequence. In comparison, a subarray is a contiguous part of a sequence. Therefore all the subarray will be subsequences too of a sequence, but vice versa is not true. For example: [1,2,4] is a subsequence for the sequence [1,2,3,4], but it is not the subarray.
2.What is the time complexity of the ZAlgorithm to search the pattern indices?
The time complexity is O(s + p), where s = size of the string and p = size of the pattern.
3.Where is the Zalgorithm used?
This algorithm is used for string searching in Gmail, Microsoft Word, Google Docs, Google Sheets, browsers, and other text editors and databases.
4.Are there more problems on Coding Ninjas Studio that deal with Data Structures and Algorithms?
Yes, Coding Ninjas Studio allows you to practice coding and offers frequently asked interview questions. The more we practice, the more our chances of landing a job at our ideal organization.
Key Takeaways
In this article, we learned to find the indices of all pattern occurrences in a string in the most efficient way using the ZAlgorithm. Since questions related to strings are frequently asked in interviews, we recommend you practice more problems based on strings on Coding Ninjas Studio.
Recommended Problems:
Are you planning to ace the interviews of reputed productbased companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!