Given two strings txt and pat, the task is to return all indices of occurrences of pat within txt, ignoring the letter case (uppercase and lowercase characters are considered same).
Examples:
Input: txt = "aBcAb", pat = "aB"
Output: [0, 3]
Explanation: The string "ab" can match with any of the following strings: "ab", "Ab", "aB" and "AB". So, pat occurs twice in txt, first occurrence starts from index 0 and second from index 3.
Input: txt = "aAAa", pat = "Aa"
Output: [0, 1, 2]
Explanation: The string "Aa" can match with any of the following strings: "aa", "aA", "Aa" and "AA". So, pat occurs thrice in txt, first occurrence starts from index 0, second from index 2 and third from index 3.
Input: txt = "abba", pat = "aC"
Output: []
Explanation: There is no occurrence of "aC" in "abba".
[Naive Approach] Matching with all substrings
The idea is, we start at every index in the text and compare it with the first character of the pattern, if they match we move to the next character in both text and pattern. Also, before matching the characters, we can convert both the characters to lower case to ignore the case. If there is a mismatch, we start the same process for the next index of the text.
C++
// C++ Program for Case Insensitive Search by matching
// with all substrings
#include <iostream>
#include <vector>
using namespace std;
vector<int> search(string &txt, string &pat) {
vector<int> res;
int n = txt.length();
int m = pat.length();
// Macth the pattern with all substrings of txt
for(int i = 0; i < n - m + 1; i++) {
bool found = true;
for(int j = 0; j < m; j++) {
// Convert the characters to lower case
if(tolower(txt[i + j]) != tolower(pat[j])) {
found = false;
break;
}
}
if(found)
res.push_back(i);
}
return res;
}
int main() {
string txt = "aBcAb", pat = "ab";
vector<int> res = search(txt, pat);
for(int idx : res)
cout << idx << " ";
}
// Java Program for Case Insensitive Search by matching
// with all substrings
import java.util.ArrayList;
import java.util.List;
class GfG {
// Method for case insensitive search by matching with all substrings
static ArrayList<Integer> search(String txt, String pat) {
ArrayList<Integer> res = new ArrayList<>();
int n = txt.length();
int m = pat.length();
// Match the pattern with all substrings of txt
for (int i = 0; i < n - m + 1; i++) {
boolean found = true;
for (int j = 0; j < m; j++) {
// Convert the characters to lower case
if (Character.toLowerCase(txt.charAt(i + j)) !=
Character.toLowerCase(pat.charAt(j))) {
found = false;
break;
}
}
// If all characters are matched, insert the index into result
if (found) {
res.add(i);
}
}
return res;
}
public static void main(String[] args) {
String txt = "aBcAb", pat = "ab";
ArrayList<Integer> res = search(txt, pat);
for (int idx : res) {
System.out.print(idx + " ");
}
}
}
# Python Program for Case Insensitive Search by matching
# with all substrings
def search(txt, pat):
res = []
n = len(txt)
m = len(pat)
# Match the pattern with all substrings of txt
for i in range(n - m + 1):
found = True
for j in range(m):
# Convert the characters to lower case
if txt[i + j].lower() != pat[j].lower():
found = False
break
# If all characters are matched, insert the index
# into result
if found:
res.append(i)
return res
if __name__ == "__main__":
txt = "aBcAb"
pat = "ab"
res = search(txt, pat)
for idx in res:
print(idx, end=" ")
// C# Program for Case Insensitive Search by matching
// with all substrings
using System;
using System.Collections.Generic;
class GfG {
static List<int> search(string txt, string pat) {
List<int> res = new List<int>();
int n = txt.Length;
int m = pat.Length;
// Match the pattern with all substrings of txt
for (int i = 0; i < n - m + 1; i++) {
bool found = true;
for (int j = 0; j < m; j++) {
// Convert the characters to lower case
if (char.ToLower(txt[i + j]) != char.ToLower(pat[j])) {
found = false;
break;
}
}
// If all characters are matched, insert the index
// into result
if (found)
res.Add(i);
}
return res;
}
static void Main() {
string txt = "aBcAb", pat = "ab";
List<int> res = search(txt, pat);
foreach (int idx in res)
Console.Write(idx + " ");
}
}
// JavaScript Program for Case Insensitive Search by matching
// with all substrings
function search(txt, pat) {
let res = [];
let n = txt.length;
let m = pat.length;
// Match the pattern with all substrings of txt
for (let i = 0; i < n - m + 1; i++) {
let found = true;
for (let j = 0; j < m; j++) {
// Convert the characters to lower case
if (txt[i + j].toLowerCase() !== pat[j].toLowerCase()) {
found = false;
break;
}
}
// If all characters are matched, insert the index
// into result
if (found) {
res.push(i);
}
}
return res;
}
// Driver Code
let txt = "aBcAb", pat = "ab";
let res = search(txt, pat);
for (let idx of res) {
console.log(idx + " ");
}
Time Complexity: O(n * m), where n is the length of txt and m is the length of pat.
Auxiliary Space: O(1)
[Expected Approach] Using KMP Algorithm
The idea is to use KMP Algorithm with the only modification to convert the characters to lowercase before comparing them during construction of lps[] array and while matching the characters.
C++
// C++ Program for Case Insensitive Search using KMP Algorithm
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void constructLps(string &pat, vector<int> &lps) {
// len stores the length of longest prefix which
// is also a suffix for the previous index
int len = 0;
// lps[0] is always 0
lps[0] = 0;
int i = 1;
while (i < pat.length()) {
// If characters match, increment the size of lps
if (tolower(pat[i]) == tolower(pat[len])) {
len++;
lps[i] = len;
i++;
}
// If there is a mismatch
else {
if (len != 0) {
// Update len to the previous lps value
// to avoid reduntant comparisons
len = lps[len - 1];
}
else {
// If no matching prefix found, set lps[i] to 0
lps[i] = 0;
i++;
}
}
}
}
vector<int> search(string &pat, string &txt) {
int n = txt.length();
int m = pat.length();
vector<int> lps(m);
vector<int> res;
constructLps(pat, lps);
// i and j, for traversing the text and pattern
int i = 0;
int j = 0;
while (i < n) {
// If characters match, move both pointers forward
if (tolower(txt[i]) == tolower(pat[j])) {
i++;
j++;
// If the entire pattern is matched
// store the start index in result
if (j == m) {
res.push_back(i - j);
// Use LPS of previous index to
// skip unnecessary comparisons
j = lps[j - 1];
}
}
// If there is a mismatch
else {
// Use lps value of previous index
// to avoid redundant comparisons
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
return res;
}
int main() {
string txt = "aBcAb";
string pat = "aB";
vector<int> res = search(pat, txt);
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
return 0;
}
// Java Program for Case Insensitive Search using
// KMP Algorithm
import java.util.ArrayList;
import java.util.List;
class GfG {
// Function to construct the LPS array
static void constructLps(String pat, int[] lps) {
// len stores the length of longest prefix which
// is also a suffix for the previous index
int len = 0;
// lps[0] is always 0
lps[0] = 0;
int i = 1;
while (i < pat.length()) {
// If characters match, increment the size of lps
if (Character.toLowerCase(pat.charAt(i)) ==
Character.toLowerCase(pat.charAt(len))) {
len++;
lps[i] = len;
i++;
}
else {
if (len != 0) {
// Update len to the previous lps value to avoid
// redundant comparisons
len = lps[len - 1];
}
else {
// If no matching prefix found, set lps[i] to 0
lps[i] = 0;
i++;
}
}
}
}
static ArrayList<Integer> search(String pat, String txt) {
int n = txt.length();
int m = pat.length();
int[] lps = new int[m];
ArrayList<Integer> res = new ArrayList<>();
// Construct the LPS array
constructLps(pat, lps);
// i and j for traversing the text and pattern
int i = 0;
int j = 0;
while (i < n) {
// If characters match, move both pointers forward
if (Character.toLowerCase(txt.charAt(i)) == Character.toLowerCase(pat.charAt(j))) {
i++;
j++;
// If the entire pattern is matched, store the start index in result
if (j == m) {
res.add(i - j);
// Use LPS of previous index to skip unnecessary comparisons
j = lps[j - 1];
}
}
else {
// If there is a mismatch
// Use LPS value of previous index to avoid redundant comparisons
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
return res;
}
public static void main(String[] args) {
String txt = "aBcAb";
String pat = "aB";
ArrayList<Integer> res = search(pat, txt);
for (int idx : res)
System.out.print(idx + " ");
}
}
# Python Program for Case Insensitive Search using KMP Algorithm
def constructLps(pat, lps):
# len_ stores the length of longest prefix which
# is also a suffix for the previous index
len_ = 0
# lps[0] is always 0
lps[0] = 0
i = 1
while i < len(pat):
# If characters match, increment the size of lps
if pat[i].lower() == pat[len_].lower():
len_ += 1
lps[i] = len_
i += 1
# If there is a mismatch
else:
if len_ != 0:
# Update len to the previous lps value
# to avoid redundant comparisons
len_ = lps[len_ - 1]
else:
# If no matching prefix found, set lps[i] to 0
lps[i] = 0
i += 1
def search(pat, txt):
n = len(txt)
m = len(pat)
lps = [0] * m
res = []
constructLps(pat, lps)
# i and j for traversing the text and pattern
i = 0
j = 0
while i < n:
# If characters match, move both pointers forward
if txt[i].lower() == pat[j].lower():
i += 1
j += 1
# If the entire pattern is matched
# store the start index in result
if j == m:
res.append(i - j)
# Use LPS of previous index to
# skip unnecessary comparisons
j = lps[j - 1]
else:
# Use lps value of previous index
# to avoid redundant comparisons
if j != 0:
j = lps[j - 1]
else:
i += 1
return res
if __name__ == "__main__":
txt = "aBcAb"
pat = "aB"
res = search(pat, txt)
for idx in res:
print(idx, end=" ")
// C# Program for Case Insensitive Search using KMP Algorithm
using System;
using System.Collections.Generic;
class GfG {
static void ConstructLps(string pat, int[] lps) {
// len stores the length of longest prefix which
// is also a suffix for the previous index
int len = 0;
// lps[0] is always 0
lps[0] = 0;
int i = 1;
while (i < pat.Length) {
// If characters match, increment the size of lps
if (Char.ToLower(pat[i]) == Char.ToLower(pat[len])) {
len++;
lps[i] = len;
i++;
}
else {
// If there is a mismatch
if (len != 0) {
// Update len to the previous lps value
// to avoid redundant comparisons
len = lps[len - 1];
}
else {
// If no matching prefix found, set lps[i] to 0
lps[i] = 0;
i++;
}
}
}
}
static List<int> Search(string pat, string txt) {
int n = txt.Length;
int m = pat.Length;
int[] lps = new int[m];
List<int> res = new List<int>();
ConstructLps(pat, lps);
// i and j for traversing the text and pattern
int i = 0;
int j = 0;
while (i < n) {
// If characters match, move both pointers forward
if (Char.ToLower(txt[i]) == Char.ToLower(pat[j])) {
i++;
j++;
// If the entire pattern is matched
// store the start index in result
if (j == m) {
res.Add(i - j);
// Use LPS of previous index to
// skip unnecessary comparisons
j = lps[j - 1];
}
}
else {
// If there is a mismatch
// Use lps value of previous index to avoid redundant comparisons
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
return res;
}
static void Main() {
string txt = "aBcAb";
string pat = "aB";
List<int> res = Search(pat, txt);
foreach (int idx in res)
Console.Write(idx + " ");
}
}
// JavaScript Program for Case Insensitive Search using
// KMP Algorithm
function constructLps(pat, lps) {
// len stores the length of longest prefix which
// is also a suffix for the previous index
let len = 0;
// lps[0] is always 0
lps[0] = 0;
let i = 1;
while (i < pat.length) {
// If characters match, increment the size of lps
if (pat[i].toLowerCase() === pat[len].toLowerCase()) {
len++;
lps[i] = len;
i++;
}
// If there is a mismatch
else {
if (len !== 0) {
// Update len to the previous lps value
// to avoid redundant comparisons
len = lps[len - 1];
}
else {
// If no matching prefix found, set lps[i] to 0
lps[i] = 0;
i++;
}
}
}
}
function search(pat, txt) {
let n = txt.length;
let m = pat.length;
let lps = new Array(m);
let res = [];
constructLps(pat, lps);
// i and j, for traversing the text and pattern
let i = 0;
let j = 0;
while (i < n) {
// If characters match, move both pointers forward
if (txt[i].toLowerCase() === pat[j].toLowerCase()) {
i++;
j++;
// If the entire pattern is matched
// store the start index in result
if (j === m) {
res.push(i - j);
// Use LPS of previous index to
// skip unnecessary comparisons
j = lps[j - 1];
}
}
// If there is a mismatch
else {
// Use lps value of previous index
// to avoid redundant comparisons
if (j !== 0)
j = lps[j - 1];
else
i++;
}
}
return res;
}
// Driver Code
let txt = "aBcAb";
let pat = "aB";
let res = search(pat, txt);
for (let i = 0; i < res.length; i++) {
console.log(res[i] + " ");
}
Time Complexity: O(n + m), where n is the length of the text and m is the length of the pattern. This is because of creating the LPS (Longest Prefix Suffix) array takes O(m) time, and the search through the text takes O(n) time.
Auxiliary Space: O(m), as we need to store the LPS array of size m.