CareerCup

use KMP string Matching.. for solution: ideone.com/t2nPA

#include<iostream>
using namespace std;
#include<string.h>
main()
{
char str[100];
cin>>str;
char c;
fflush(stdin);
c=getchar();
int i,len;
len=strlen(str);
i=0;
while(c!='\n')
{
if(c==str[i])
{
i++;
if(i==len)
{
cout<<"matched";
break;
}
}
else if(c==str[0])
{
i=1;
}
else
{
i=0;
}
c=getchar();
}
if(c=='\n')
cout<<"Did Not Match";
}

rabin-karp algorithm

Make a finite automation from the string to be searched. Process each character from the stream and update the state of the automation. If at any time we are on the accepting state, declare the result. [ Cormen Chapter 32, Section 32.3]

We can't use Rabin-Karp as the question says we can't store the stream ( which I take it as we are not even allowed to store the string of size equal to the string to find. In Rabin-Karp, once we find the match, we need to verify whether it actually matches ).

Knuth–Morris–Pratt algorithm
prepocess the str so tat we dont need to store the stream

If there is no repetition of the first element of the string, the algorithm should be pretty easy. Otherwise, we need to keep an array of matching positions, the size of which is the times of repetition of the first element.

is this for SDET?

Let len be the number of chars in str. Store the incoming characters of the stream in a queue of len elements. Every time you accept a new char from the stream, append the new character to the one end and dequeue a character from the opposite end. Check if the character sequence stored in the queue is equal to str. If so, then set a global bool variable to true.

@Anonymous and @leet one problem is that string does'nt have attribute length. its a method in String str.length(); not str.lengtth;

The code is in C

Function returns 0 on failure and 1 on success

int match_str(char str[])
{
char ch,*temp=str;
int len,count=0;
for(len=0;str[len];len++);
while(scanf("%c",&ch))
{
if(ch=='\n')
break;
if(*temp!=ch && count)
{
temp=str;count=0;
}
if(*temp==ch)
{
temp++;count++;
}
if(count==len-1)
return 1;
}
return 0;
}

#include<iostream>
using namespace std;
#include<string.h>
main()
{
char str[100];
cin>>str;
char c;
fflush(stdin);
c=getchar();
int i,len;
len=strlen(str);
i=0;
while(c!='\n')
{
if(c==str[i])
{
i++;
if(i==len)
{
cout<<"matched";
break;
}
}
else if(c==str[0])
{
i=1;
}
else
{
i=0;
}
c=getchar();
}
if(c=='\n')
cout<<"Did Not Match";
}

{{
int j = 0;
int result = -1;
for(int i=0; string[i] && find[j]; ++i)
{
if(string[i] != find[j]){ j=0;}
if(string[i] == find[j]){
if(j == 0){ result = i; }
j+= 1;
}
}

return find[j] == 0 ? result : -1;
}}

you do 1 thing.first find the size of string str.then search that lenght @ 1 time .means read 1 character match that with the character in str.if same move forward else discard that character and move next.

boolean MatchString(Stream stream, String str)
   {
      boolean done= false;
      int i = 0;
      while(!done)
       {
            char c = stream.readNextChar();
            if(str.charAt(i) == c )
            {
                if(i == (str.length-1))
                 {
                     return true;
                 }
                 i++;                
            } 
            else
           {
               i = 0;
            }
        }
   }