Simple brute force how to optimize?


#1

i havent thought about any optimizing algorithm cause i didn’t need to as it accepted the simple brute force solution but can it be optimized using any well known algorithm?


#2

using kmp algorithm time complexity O(m + n)
in java
public class Solution {
// DO NOT MODIFY THE ARGUMENTS WITH “final” PREFIX. IT IS READ ONLY
public int strStr(final String s, final String t) {
if (t.length() == 0)
{
return -1;
}
int i, j = t.length();
int [] arr = new int[t.length() + 1];
int k = 0;
for (i = 2; i < arr.length; ++i)
{
if(t.charAt(i - 1) == t.charAt(k))
{
k++;
arr[i] = k;
}
else if (k != 0)
{
k = arr[k];
i–;
}
}
k = 0;
for (i = 0; i < s.length(); ++i)
{
if (s.charAt(i) == t.charAt(k))
{
k++;
if (k == j)
{
return i - j + 1;
}
}
else if (k != 0)
{
k = arr[k];
i–;
}
}
return -1;
}
}