Salesforce Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
You cannot take help of any of the data structure. This is what I figured out.
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package strcheck;
/**
*
* @author Sushant
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
String mainString = "abcdefghcd"; //'This is an Example';
String find = "cde";
if (mainString ==null || find ==null|| (mainString.length()<=find.length())) {
return;
}
int count = 0, j = 0;
boolean flag = false;
for(int i = 0 ; i < mainString.length(); i++)
{
if(mainString.charAt(i) == find.charAt(j))
{
int temp = i+1;
for(j = 1; j < find.length(); j++)
{
if(mainString.charAt(temp)== find.charAt(j))
{
temp++;
flag = true;
}
else
{
flag = false;
break;
}
}
if(flag)
{
count++;
}
}
}
System.out.println(" "+count);
}
}
This is simple brute force technique. It will take O(n*L) where n = size of "str" and L = size of "find"
public class substringCount {
public static void main(String[] args){
System.out.println("\nEnter String and find:");
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String find = sc.nextLine();
substring(str,find);
}
private static void substring(String str, String find) {
// TODO Auto-generated method stub
int s=0,count=0;
for(int i=0;i<str.length();i++){
if(s!=find.length() && str.charAt(i)==find.charAt(s))
s++;
else if(s>0){
s=0;
}
if(s==find.length()){
count++;
s=0;
}
}
System.out.println("\nCount is : "+count);
}
}
this should only take O(given string) time!
Why would it do in linear time? I don't think so because your second loop, which is implicit one is where s is being reset to zero.
public static int subStrOcc(String str,String sub)
{
int strSubLen = sub.length();
int strLen = str.length();
int jValue=0;
int subCount=0;
if(strSubLen>=1)
{
for(int iCtr =0; iCtr<strLen; iCtr++)
{
if(str.charAt(iCtr)==sub.charAt(jValue))
{
jValue++;
if(jValue==strSubLen)
{
subCount++;
jValue=0;
}
}
else
{
jValue=0;
}
}
}
return subCount;
}
The following snippet handles overlapping string cases as well:
s = "55555"
ss = "555"
result: 1
s = "abcdefghcde";
ss = "cde"
result: 2
public static int count(String s, String ss) {
int count = 0;
for (int i = 0 ; i < s.length() ; i++) {
int pos = 0;
if (s.charAt(i) == ss.charAt(pos)) {
pos++;
while ((i + pos) < s.length() && pos < ss.length()) {
if (s.charAt(i + pos) != ss.charAt(pos)) {
break;
}
if (pos == ss.length() -1) {
count++;
i += ss.length();
}
pos++;
}
}
}
return count;
Actually, i += ss.length(); should be i += ss.length() -1; to properly handle the overlap case.
to test:
s = "555555"
ss = "555"
result: 2
s = "55555"
ss = "555"
result: 1
public static int count(String s, String ss) {
int count = 0;
for (int i = 0 ; i < s.length() ; i++) {
int pos = 0;
if (s.charAt(i) == ss.charAt(pos)) {
pos++;
while ((i + pos) < s.length() && pos < ss.length()) {
if (s.charAt(i + pos) != ss.charAt(pos)) {
break;
}
if (pos == ss.length() -1) {
count++;
i += ss.length() -1;
}
pos++;
}
}
}
return count;
}
import java.util.*;
import java.lang.*;
public class Firstocc {
/**
* @param args
*/
public static void main(String[] args)throws Exception {
String s="";
String ms=" ";
String sub="";
boolean b=false;
Scanner sc=new Scanner(System.in);
System.out.print("enter the actual string");
s=sc.next();
System.out.print("enter the searching string");
sub=sc.next();
int subl=sub.length();
System.out.print(subl);
int n=s.length()-subl;
for(int i=0;i<n;i++)
{
ms=s.substring(i,subl);
//System.out.println("matching string is"+ms);
if(sub.equalsIgnoreCase(ms))
{
b=true;
System.out.println("matching string first occurance position id:"+i);
exit(0);
}
subl++;
}
if(!b)
{
System.out.println("string doesn't match");
}
}
private static void exit(int i) {
System.exit(0);
}
}
sample o/p:
enter the actual stringabcdcdefcd
enter the searching stringcd
no time match occur :3
Here is my solution, it does not use brute -force nor substring method:
import java.util.Arrays;
public class SubStringCount {
public static void main(String[] args) {
System.out.println(count("abcdefghcde", "cde"));
}
public static int count(String s, String sub){
int counter = 0;
String temp;
char [] c = s.toCharArray();
for (int i = 0; i + sub.length() <= s.length(); i++) {
// Copies the specified range of the specified array into a new array
//then, using string constructor, char array is converted into string
temp = new String(Arrays.copyOfRange(c, i, i+sub.length()));
if(temp.equals(sub))
counter++;
}
return counter;
}
}
i have tried ur code.......... it cannot resolve cpyofrange func........ What will be the problem..........?
So your version is 1.4, so this should work for you:
public class SubStringCount {
public static void main(String[] args) {
System.out.println(count("aaaaa", "aaa"));
}
public static int count(String s, String sub){
int counter = 0;
String temp;
char [] c = s.toCharArray();
for (int i = 0; i + sub.length() <= s.length(); i++) {
// Copies the specified range of the specified array into a new array
//using string constructor, char array in converted into string
temp = new String(copyOfRange(c, i, i+sub.length()));
if(temp.equals(sub))
counter++;
}
return counter;
}
public static char[] copyOfRange(char[] original, int from, int to) {
int newLength = to - from;
if (newLength < 0)
throw new IllegalArgumentException(from + " > " + to);
char[] copy = new char[newLength];
System.arraycopy(original, from, copy, 0,
Math.min(original.length - from, newLength));
return copy;
}
}
Let me know.
my Try............
import java.io.*;
class Substr
{
public static void main(String a[])
{
DataInputStream dis =new DataInputStream(System.in);
String src,sub;
int count=0,i,j,n1,n2;
try
{
System.out.println("Enter the source string ");
src=dis.readLine();
System.out.println("Enter the Sub string ");
sub=dis.readLine();
n1=src.length();
n2=sub.length();
for(i=0,j=0;i<n1;)
{
if(src.charAt(i)==sub.charAt(j))
{
i++;
j++;
if(j==n2)
{
count=count+1;
j=0;
}
}
else
{
i=i-j+1;
j=0;
}
}
System.out.println(count);
}
catch(IOException e)
{
System.out.println(e);
}
}
}
This is O(N^2) but will work:
public static int countSubString(String str, String subStr){
char[] strArr = str.toCharArray();
int len = strArr.length;
char[] subStrArr = subStr.toCharArray();
int lenSubStr = subStrArr.length;
int countMatches = 0;
for(int i=0;i<len;i++){
if(strArr[i] == subStrArr[0]){
boolean match = false;
for(int j=1;j<lenSubStr;j++){
if(strArr[i+j] == subStrArr[j]){
match = true;
} else{
match = false;
}
}
if(match){
countMatches++;
i = i+lenSubStr-1;
}
}
}
return countMatches;
}
private static boolean checkOthers(char stri[],char finds[],int mainpos){
for(int i=1;i<finds.length;i++){
if(stri[mainpos++] != finds[i]){
return false;
}
}
return true;
}
public static void main(String[] args) {
String str = "aaaaaaaaa";
String find = "aaa";
int count=0;
char stri[] = str.toCharArray();
char finds[] = find.toCharArray();
for (int i = 0; i < stri.length-(finds.length-1); i++) {
if(stri[i] == finds[0]){
if(checkOthers(stri,finds,i+1)){
count++;
i = i+finds.length-1;
}
}
}
System.out.println(count);
}
public class JavaApplication1 {
public static void main(String[] args) {
int count=0;
String a=("abcdenmgcdkjlocdpghrcdhellocdcdcd");
int n=a.length();
String find=("cd");
for(int j=0;j<2;j++){
for(int i=0;i<n;i++){
if(a.charAt(i)==find.charAt(j)&&a.charAt(i+1)==find.charAt(j+1))
{
count++;
}
}
System.out.println(""+count);
}
}
}
import java.io.*;
public class SubStringCount
{
public static void main(String arg[])throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter you string:");
String s1=br.readLine();
System.out.println("Enter the substring");
String s2=br.readLine();
int i=0;int j=0;
char[] str=s1.toCharArray();
char[] sub=s2.toCharArray();
int count=0;
while(i<str.length)
{
if(str[i]==sub[j])
{
j++;
}
else
{
j=0;
}
if(j==sub.length)
{
j=0;
count++;
}
i++;
}
}
}
It a little like kmp, but the fail table is not build before running, it's build dynamically during running.
public static int substringCount(String s, String t) {
int l = s.length();
int n = t.length();
int m, i;
m = i = 0;
int count = 0;
int T[] = new int[n];
T[0] = -1;
while (m < l) {
//System.out.print("m: " + m + " i: " + i + " T: " + T[i]);
if (i > 0 && T[i - 1] == -1) {
if (s.charAt(m + i) == t.charAt(0)) {
T[i] = 0;
} else {
T[i] = -1;
}
} else if (i > 0 && T[i - 1] >= 0) {
if (s.charAt(m + i) == t.charAt(T[i - 1]+1))
T[i] = T[i - 1] + 1;
else
T[i] = T[i - 1];
}
//System.out.println(" T:" + T[i]);
if (s.charAt(m + i) == t.charAt(i)) {
i++;
if (i == n ) {
count++;
m += i;
i = 0;
}
} else {
m = m + i - T[i];
if (T[i] > 0) {
i = T[i];
} else {
i = 0;
}
}
}
return count;
}
In salesforce occurrence count can be done using below method
String s='I am quite sure as well as there is no clue to traverse a string without inbuilt methods';
System.debug(s.countMatches('as'));
Also we can use some combination of inbuilt function to establish the same functionality.
In salesforce it's bit typical task as we can't iterate string letters using any loop and can't define character datatype.
Using salesforce string function
String s='asasdadddasdaasdsdsdssddsdddsdsassasdsdadffffffas';
System.debug(s.countMatches('as'));
or
We can't travers a string characters directly using any forloop and char datatype is not available to convert a string into characters. So we can establish this functionality using combination of some other string methods as well rather than using direct method to count no. of occurrences.
Let me know if it is possible to iterate stringUsing salesforce string function
String s='asasdadddasdaasdsdsdssddsdddsdsassasdsdadffffffas';
System.debug(s.countMatches('as'));
or
We can't travers a string characters directly using any forloop and char datatype is not available to convert a string into characters. So we can establish this functionality using combination of some other string methods as well rather than using direct method to count no. of occurrences.
Let me know if it is possible to iterate stringUsing salesforce string function
String s='asasdadddasdaasdsdsdssddsdddsdsassasdsdadffffffas';
System.debug(s.countMatches('as'));
or
We can't travers a string characters directly using any forloop and char datatype is not available to convert a string into characters. So we can establish this functionality using combination of some other string methods as well rather than using direct method to count no. of occurrences.
Let me know if it is possible to iterate string
I tested this , it works fine(Null checks and condition to check if original string is less than substring, those were missing.)
public static void main(String args[]){
String origStr = "bbbabcmnabckabcab";
String subStr= "abc";
int subC =0;
int totC= 0;
for(int i=0;i<origStr.length();i++){
if(origStr.charAt(i) == subStr.charAt(subC)){
subC++;
if(subStr.length()==subC++){
totC++;
subC =0;
}
}
}
System.out.println("count:"+totC);
}
private static int countStringOccurence(String s1, String s2) {
int s1Length = s1.length();
int s2Length = s2.length();
int result = 0;
if (s1Length - s2Length < 0)
return 0;
for (int s1Idx = 0; s1Idx < s1Length - s2Length + 1; s1Idx++) {
if (isPresent(s1, s2, s1Idx)) {
result++;
s1Idx += s2Length - 1;
}
}
return result;
}
private static boolean isPresent(String s1, String s2, int s1Idx) {
for (int s2Idx = 0; s2Idx < s2.length(); s2Idx++) {
if (s1.charAt(s1Idx) != s2.charAt(s2Idx))
return false;
s1Idx++;
}
return true;
}
public int countSubString(final String inputString, final String subString) {
int count = 0;
boolean matchFound = false;
for (int i = 0; i < inputString.length(); i++) {
if(inputString.charAt(i) == subString.charAt(0)) {
matchFound = false;
for(int j = 0; j<subString.length(); j++) {
if(inputString.length() <= i+j || inputString.charAt(i+j) != subString.charAt(j)) {
matchFound = false;
break;
}
matchFound = true;
}
}
if(matchFound) {
matchFound = false;
count++;
}
}
return count;
}
public static int countSubstring(String literal, String substring) {
int i = 0;
int j = 0;
int count = 0;
while (i < literal.length()) {
if (literal.charAt(i) == substring.charAt(j) || literal.charAt(i) == substring.charAt(0)) {
if (literal.charAt(i) == substring.charAt(0))
j = 1;
else
j++;
i++;
if (j == substring.length()) {
count++;
j = 0;
}
} else {
i++;
j = 0;
}
}
return count;
}
public int SubStringCount(string inputString, string find)
{
int count = 0;
for (int j = 0; j < inputString.Length; j++)
{
for (int i = 0; i < find.Length; i++)
{
if (j<inputString.Length && find[i] == inputString[j])
{
++j;
if (i + 1 == find.Length)
{
++count;
--j;
break;
}
}
else
{
--j;
break;
}
}
}
Console.WriteLine("The count of '{0}' in '{1}' is {2}", find, inputString, count);
return count;
}
/**
* Counts the number of occurrences.
*/
public class OccurrencesFinder {
public static void main(String[] args) {
System.out.println("Number of occurrences of c: " + new OccurrencesFinder().count("abcdcdcdedcdfghcde", "c"));
System.out.println("---------------------");
System.out.println("Number of occurrences of cd: " + new OccurrencesFinder().count("abcdcdcdedcdfghcde", "cd"));
System.out.println("---------------------");
System.out.println("Number of occurrences of cde: " + new OccurrencesFinder().count("abcdcdcdedcdfghcde", "cde"));
System.out.println("---------------------");
System.out.println("Number of occurrences of cdcd: " + new OccurrencesFinder().count("abcdcdcdedcdfghcde", "cdcd"));
System.out.println("---------------------");
}
public int count(String string, String findableString) {
int count = 0;
for(int i = 0; i < string.length(); i++) {
if(string.charAt(i) == findableString.charAt(0)) {
if(checkRestOfCharsMatch(string, findableString, i+1, 1)) {
System.out.println("Found at index: " + i);
count++;
}
}
}
return count;
}
private boolean checkRestOfCharsMatch(String string, String findableString, int stringIndex, int findableStringIndex) {
while(stringIndex < string.length() && findableStringIndex < findableString.length()) {
if(string.charAt(stringIndex) != findableString.charAt(findableStringIndex)) {
return false;
}
findableStringIndex++;
stringIndex++;
}
return true;
}
}
/**
* Counts the number of occurrences.
*/
public class OccurrencesFinder {
public static void main(String[] args) {
System.out.println("Number of occurrences of c: " + new OccurrencesFinder().count("abcdcdcdedcdfghcde", "c"));
System.out.println("---------------------");
System.out.println("Number of occurrences of cd: " + new OccurrencesFinder().count("abcdcdcdedcdfghcde", "cd"));
System.out.println("---------------------");
System.out.println("Number of occurrences of cde: " + new OccurrencesFinder().count("abcdcdcdedcdfghcde", "cde"));
System.out.println("---------------------");
System.out.println("Number of occurrences of cdcd: " + new OccurrencesFinder().count("abcdcdcdedcdfghcde", "cdcd"));
System.out.println("---------------------");
System.out.println("Number of occurrences of cdcd: " + new OccurrencesFinder().count("abcdcdcdedcdfghcde", "ded"));
}
public int count(String string, String findableString) {
int count = 0;
for(int i = 0; i < string.length(); i++) {
if(string.charAt(i) == findableString.charAt(0)) {
if(checkRestOfCharsMatch(string, findableString, i+1, 1)) {
System.out.println("Found at index: " + i);
count++;
}
}
}
return count;
}
private boolean checkRestOfCharsMatch(String string, String findableString, int stringIndex, int findableStringIndex) {
while(stringIndex < string.length() && findableStringIndex < findableString.length()) {
if(string.charAt(stringIndex) != findableString.charAt(findableStringIndex)) {
return false;
}
findableStringIndex++;
stringIndex++;
}
return findableStringIndex == findableString.length(); // Missed this. We have to see that the complete string is matched at the end.
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
String str="aaaaaaa";
String substr="aa";
System.out.println(remainingString(str,substr));
}
static String remainingString(String str,String substr)
{
if(str==null || substr==null)
return null;
int i=0,counter=0;
for(i=0;i<str.length()-substr.length();i++)
{
if(str.substring(i,i+substr.length()).equals(substr))
{
i=i+substr.length();
break;
}
}
return str.substring(i,str.length());
}
}
def find_number_of_substrings(string, substring):
substring_length = len(substring)
number_of_substrings = 0
for char_position, char in enumerate(string):
remaining_chars = len(string) - char_position
if substring_length > remaining_chars:
return number_of_substrings
found = True
if char == substring[0]:
for sub_char_position, sub_char in enumerate(substring):
idx_outer = char_position + sub_char_position
char_outer = string[idx_outer]
if sub_char != char_outer:
found = False
break # do not + 1 number of substrings
if found:
number_of_substrings += 1
return number_of_substrings
n = find_number_of_substrings('abcdefghcdecd', 'cde')
public class FindSubStringCount{
//T(n) = O(n)
public int findSubStringCount(String s1, String s2){
if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0 || s1.length() < s2.length()){
return 0;
}
char [] chr1 = s1.toCharArray();
char [] chr2 = s2.toCharArray();
int count = 0;
for(int i = 0; i < chr1.length; i++){
int j = 0;
if(chr1[i] == chr2[j]){
while(j < chr2.length){
if(chr1[i] != chr2[j]){
i--;
break;
}
i++;
j++;
}
if(j == chr2.length){
count++;
}
}
}
return count;
}
public static void main(String[] args) {
FindSubStringCount f = new FindSubStringCount();
System.out.println(f.findSubStringCount(args[0], args[1]));
}
}
package com.concurrency.pkg;
public class SubstrCount {
private static int cntSubStr(char[] c1, char[] c2) {
int cnt = 0;
int k = 0;
int n = 0;
for (int j = 0; j < c1.length && k < c2.length;) {
n++;
if (c2[k] == c1[j]) {
j++;
k++;
if (k == c2.length) {
cnt += 1;
k = 0;
}
continue;
}
k = 0;
j = n;
}
return cnt;
}
public static void main(String[] args) {
char[] s1 = "abghefghcde".toCharArray();
char[] s2 = "gh".toCharArray();
System.out.println(cntSubStr(s1, s2));
}
}
public class P3_FindOccuranceOfSubStringInStringWithOutIUsingFun {
public static void main(String[] args) {
String str = "cdcde";
String input = "cde";
// cdcde, abcdefghcgde
String flag = "";
char[] strChar = str.toCharArray();
char[] inputChar = input.toCharArray();
int count = 0;
int i = 0, j = 0;
int numberOfInputs = 0;
while (count <= strChar.length - 1) {
// if (strChar[i] == inputChar[j]) {
int k = count;
j = 0;
while (j <= inputChar.length - 1) {
if (strChar[k] == inputChar[j]) {
flag = "found";
} else {
flag = "not found";
break;
}
k++;
j++;
}
if (flag.equalsIgnoreCase("found")) {
numberOfInputs++;
}
count++;
}
System.out.println("numberOfInputs : " + numberOfInputs);
}
}
package com.dev;
public class P3_FindOccuranceOfSubStringInStringWithOutIUsingFun {
public static void main(String[] args) {
String str = "cdcde";
String input = "cde";
// cdcde, abcdefghcgde
String flag = "";
char[] strChar = str.toCharArray();
char[] inputChar = input.toCharArray();
int count = 0;
int i = 0, j = 0;
int numberOfInputs = 0;
while (count <= strChar.length - 1) {
// if (strChar[i] == inputChar[j]) {
int k = count;
j = 0;
while (j <= inputChar.length - 1) {
if (strChar[k] == inputChar[j]) {
flag = "found";
} else {
flag = "not found";
break;
}
k++;
j++;
}
if (flag.equalsIgnoreCase("found")) {
numberOfInputs++;
}
count++;
}
System.out.println("numberOfInputs : " + numberOfInputs);
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
public class FindSubstring {
static int flag = 0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out, true);
public static void main(String[] args) {
// TODO Auto-generated method stub
FindSubstring fstr = new FindSubstring();
fstr.subStringFinder("Hello", "HelloHelloBHello");
}
public void subStringFinder(String searchStr, String orignalStr){
if(searchStr.isEmpty() || orignalStr.isEmpty() || (searchStr.length() > orignalStr.length()) ){
return;
}
int i = 0;
for(int orgChar = 0 ; orgChar < orignalStr.length(); orgChar++){
if(orignalStr.charAt(orgChar) == searchStr.charAt(i) ){
pw.println(orignalStr.charAt(orgChar));
++i;
}
else if (i !=0)
{ i = 0;
orgChar --;
}
if(i == searchStr.length()) {
flag++;
i = 0;
}
}
if( flag != 0){
pw.printf("Substring occured %d time", flag );
}
else {
pw.println("Substring is not present");
}
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
public class FindSubstring {
static int flag = 0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out, true);
public static void main(String[] args) {
// TODO Auto-generated method stub
FindSubstring fstr = new FindSubstring();
fstr.subStringFinder("Hello", "HelloHelloBHello");
}
public void subStringFinder(String searchStr, String orignalStr){
if(searchStr.isEmpty() || orignalStr.isEmpty() || (searchStr.length() > orignalStr.length()) ){
return;
}
int i = 0;
for(int orgChar = 0 ; orgChar < orignalStr.length(); orgChar++){
if(orignalStr.charAt(orgChar) == searchStr.charAt(i) ){
pw.println(orignalStr.charAt(orgChar));
++i;
}
else if (i !=0)
{ i = 0;
orgChar --;
}
if(i == searchStr.length()) {
flag++;
i = 0;
}
}
if( flag != 0){
pw.printf("Substring occured %d time", flag );
}
else {
pw.println("Substring is not present");
}
}
}
C# Solution
Tests:
"Let's take LeetCode contest", "take", -> 6
"Let's take LeetCode contest", "Leet" -> 11
"cdcde", "cde" -> 2
"cdcde", "cdex", -> -1
"cd", "cdex", -> -1
"", "sdsd" -> -1
"ssss", "", -> -1
public static int IndexOf(string source, string find)
{
if (string.IsNullOrEmpty(source) || string.IsNullOrEmpty(find))
{
return -1;
}
var sourceLength = source.Length;
if (find.Length > sourceLength)
{
return -1;
}
var findPosition = 0;
var findLength = find.Length;
for (int i = 0; i < sourceLength; i++)
{
if (findPosition == findLength)
{
return i - findPosition;
}
if (source[i] == find[findPosition])
{
findPosition++;
}
else if (source[i] == find[0])
{
findPosition = 1;
}
else
{
findPosition = 0;
}
}
//matching at the end of the string.
if (findPosition == findLength)
{
return source.Length - findPosition;
}
return -1;
}
public class StringPattern {
public int[] prefixTable(char P[], int m) {
int i=1, j=0;
int F[] = new int[m];
while(i < m) {
if (P[i] == P[j]) { //matching chars
F[i] = j + 1;
i++;
j++;
} else if (j > 0) { //not matching chars and resetting j counter if it is more than 0
j = F[j - 1];
} else {
F[i] = 0; //not matching chars and setting 0
i++;
}
}
System.out.println("\t"+ "Printing Prefix Pattern Table");
for(int k=0; k < m; k++){
System.out.print("\t"+F[k]);
}
return F;
}
public int kmpMatching(char T[], int n, char P[], int m){
int i=0, j=0;
int[] F = prefixTable(P,m);
int counter = 0;
while(i < n){
if(T[i] == P[j]){ // matching char
if(j==m-1){ // checking the pattern reached completely
//return i-j;
++counter;
j=0;
System.out.println("matching pattern ::");
}
else {
i++;
j++;
}
}
else if(j>0) {
j = F[j-1];
}
else i++;
}
return counter;
}
public static void main(String args[]){
// char T[] = {'b','a','c','b','a','b','a','b','a','b','a','c','a','c','a'};
// char P[] = {'a','b','a','b','a','c','a'};
char T[] = {'a','a','b','c','d','e','a','b','c','a','a','b','a','b','c','d'};
char P[] = {'a','b','c'};
StringPattern sp = new StringPattern();
int match= sp.kmpMatching(T,T.length,P,P.length);
System.out.println("String Patterns count "+match);
}
}
public class StringPattern {
public int[] prefixTable(char P[], int m) {
int i=1, j=0;
int F[] = new int[m];
while(i < m) {
if (P[i] == P[j]) { //matching chars
F[i] = j + 1;
i++;
j++;
} else if (j > 0) { //not matching chars and resetting j counter if it is more than 0
j = F[j - 1];
} else {
F[i] = 0; //not matching chars and setting 0
i++;
}
}
System.out.println("\t"+ "Printing Prefix Pattern Table");
for(int k=0; k < m; k++){
System.out.print("\t"+F[k]);
}
return F;
}
public int kmpMatching(char T[], int n, char P[], int m){
int i=0, j=0;
int[] F = prefixTable(P,m);
int counter = 0;
while(i < n){
if(T[i] == P[j]){ // matching char
if(j==m-1){ // checking the pattern reached completely
//return i-j;
++counter;
j=0;
System.out.println("matching pattern ::");
}
else {
i++;
j++;
}
}
else if(j>0) {
j = F[j-1];
}
else i++;
}
return counter;
}
public static void main(String args[]){
// char T[] = {'b','a','c','b','a','b','a','b','a','b','a','c','a','c','a'};
// char P[] = {'a','b','a','b','a','c','a'};
char T[] = {'a','a','b','c','d','e','a','b','c','a','a','b','a','b','c','d'};
char P[] = {'a','b','c'};
StringPattern sp = new StringPattern();
int match= sp.kmpMatching(T,T.length,P,P.length);
System.out.println("String Patterns count "+match);
}
}
public class B {
public static void main(String[] args) {
String input = "abdfdefghcedcee";
String find = "dfde";
char[] ic = input.toCharArray();
char[] fc = find.toCharArray();
int count=0;
for(int i=0;i<ic.length;i++)
{
//System.out.println(i);
char c=0;
String tmp="";
for(int j =0;j<fc.length;j++)
{
if(i+j<ic.length)
{
c=ic[i+j];
tmp=tmp+c;
}
}
System.out.println(i+"--->"+tmp);
if(tmp.equals(find))
count++;
}
System.out.println(count);
}
}
If space is no issue, you can use suffix tree. Time complexity: O(query length)
- HauntedGhost March 05, 2013Or you can use KMP algorithm it requires lesser space than suffix tree.