CareerCup

def prefix(st, text, str_len):
    i = 0
    while st[i] == text[i] and str_len:
        str_len -= 1
        if str_len:
            i += 1

    if not str_len:
        return True
    else:
        return ord(st[i]) - ord(text[i])


def strstr(st, text):
    str_len = len(st)
    for i in range(len(text) - len(st)+1):
        if type(prefix(st, text[i:], str_len)) == bool:
            return i

    return -1

If the program is going to be used only once. What the tip suggests is good enough. Taking O(nm) time, where n is the length of the longer string and m is the length of the shorter one.

If it is going to be used many times for checking different substrings, first build the surffix tree of the long string. Then checking a substring of length m only takes O(m) time.

public static int getSubStringStartingPosition(char[] st1, char[] st2)
	{
		int pos=0;
		boolean flag=false;
		
		int k=0;
		for (int i=0; i<=st1.length-1; ++i)
		{
			if ((k <= st2.length-1) && (st1[i]==st2[k]))
			{
				//System.out.println("found.."+st2[k]);
				if (!flag)
				{
					pos=i;
				}
					
				flag=true;
				k++;
			}
			else
			{
				System.out.println("not found.."+st1[i]);
				if (flag && k <=st2.length-1)
				{
					System.out.println("found an extra character in the middle..");
					pos=-1;
				}
			}
		}
		return pos;
	}

｛｛

var indexOf = function(search, target){

for(var k = 0; k < search.length; k++){

if(search[k] = target[0]){

var found = true;

for(var j = 0; j < target.length; j++){

found = found & (search[k + j] == target[j]);

}

if(found){

return k;

}

}

}

return -1;


}

console.log(indexOf('this works','works'));
console.log(indexOf('AAAB','AAB'));

｝｝

public String findThisInString(String string1, String string2)
	{
		int index = string1.indexOf(string2);
		return String.format("Found '%s' at index: %d", string2, index);
	}

public String findThisInString(String string1, String string2)
	{
		int index = string1.indexOf(string2);
		return String.format("Found '%s' at index: %d", string2, index);
	}

KMP (easy if you know that)

vector<int> BuildPrefixFunction(const string& s) {
  vector<int> result(s.length(), 0);
  for (int i = 1; i < s.length(); ++i) {
    int j = result[i-1];
    while (j && s[i] != s[j]) j = result[j-1];
    if (s[i] == s[j]) ++j;
    result[i] = j;
  }
  return result;
}

Z function (Google that)

But would prefer hash here. Polynomial hashes would work perfectly here.

KMP (easy if you know that)

vector<int> BuildPrefixFunction(const string& s) {
  vector<int> result(s.length(), 0);
  for (int i = 1; i < s.length(); ++i) {
    int j = result[i-1];
    while (j && s[i] != s[j]) j = result[j-1];
    if (s[i] == s[j]) ++j;
    result[i] = j;
  }
  return result;
}

Z function (Google that)

But would prefer hash here. Polynomial hashes would work perfectly here.

#include<stdio.h>
#include<string.h>
#define MAX 80
int find();
int main()
{
int n;
n=find();
if (n!=0)
printf("\n First occurence of first string is at %d position of second string", n);
else
printf("\n Not found!");
return(0);

}

int find()
{
char str2[MAX],str1[MAX],*str3;
int len2,i,n=0;
printf("Enter the first string:\n");
gets(str1);
printf("Enter the second string:\n");
gets(str2);
len2=strlen(str2);

for (i=0;i<len2;i++)
{
if (str2[i]==str1[0])
{
str3=strstr(str2,str1);
printf("\n Found...:\t %s", str3);
n=i;
break;
}
else
n=0;
}
return (n);
}

Here i am giving it in shell script with the help of awk

Var1=<String1>
Var2=<String2>

echo $Var2 |awk -v Var=$Var1 '{print index($0,Var)}'

int indexOf(String a, String b) {
if (a == null || a.isEmpty() || b == null || b.isEmpty())
return -1;
if (a.length() > b.length())
return -1;
int max = b.length() - a.length() + 1;
int bx = 0;
while (bx < max) {
if (a.charAt(0) != b.charAt(bx)) {
bx++;
while (bx< max && a.charAt(0) != b.charAt(bx)) {
bx++;
}
} else {
boolean found = true;
for (int i = 1; i < a.length() && bx + i < b.length(); i++) {
if (a.charAt(i) != b.charAt(bx + i)) {
found = false;
break;
}
}
if (found)
return bx;
bx++;
}
}
return -1;
}

int indexOf(String a, String b) {
		if (a == null || a.isEmpty() || b == null || b.isEmpty())
			return -1;
		if (a.length() > b.length())
			return -1;
		int max = b.length() - a.length() + 1;
		int bx = 0;
		while (bx < max) {
			if (a.charAt(0) != b.charAt(bx)) {
				bx++;
				while (bx< max && a.charAt(0) != b.charAt(bx)) {
					bx++;
				}
			} else {
				boolean found = true;
				for (int i = 1; i < a.length() && bx + i < b.length(); i++) {
					if (a.charAt(i) != b.charAt(bx + i)) {
						found = false;
						break;
					}
				}
				if (found)
					return bx;
				bx++;
			}
		}
		return -1;
	}

he easy C++ way to do this is to use std::string::find:

std::string s = "apple";
std::string sub = "ple";
auto index = s.find(sub); //std::string::npos if not found
The way for C would be strstr:

const char *s = "apple";
const char *sub = "ple";
const char *pos = strstr(s, sub); //NULL if not found

Worst case Complexity : O(n)

public class Practice65 {
	public static void main(String args[]){
		String str1 = "abcdefcde";
		String str2 = "de";
		int j=0,i=0;
		while(i<str1.length()){
			if(str2.charAt(j) == str1.charAt(i)){
				j++;
				i++;
				if(j == str2.length()){
					System.out.println(i - str2.length());
					break;
				}
			}else{
				j=0;
				i++;
			}
		}
	}
}

Use KMP algo.