OJ Board

Code: Select all

#include <stdio.h>
#define MAX 1000000

int FailureFunction[MAX];
char Text[MAX];
char Pattern[MAX];


void KMPFailureFunction() {
	int length;
	int i, j;
	length = strlen(Pattern);
	i = 1;
	j = 0;
	while(i < length) {
		if(Pattern[j] == Pattern[i]) {
			FailureFunction[i] = j+1;
			i++;
			j++;
		}
		else if(j>0) j=FailureFunction[j-1];
		else {
			FailureFunction[i] = 0;
			i++;
		}
	}
}


int KMPMatch() {
	int i, j, text_length, pattern_length;

	KMPFailureFunction();
	text_length = strlen(Text);
	pattern_length = strlen(Pattern);
	i = j = 0;
	while(i<text_length) {
		if(Pattern[j] == Text[i]) {
			i++;
			j++;
			if(j==pattern_length) return 1;
		}
		else if(j>0) j = FailureFunction[j-1];
		else i++;
	}
	return 0;
}


int main() {
	int rep;
	int pat_num;

	scanf("%d\n", &rep);
	while(rep--) {
		scanf("%s\n", Text);
		scanf("%d\n", &pat_num);
		while(pat_num--) {
			scanf("%s", Pattern);

			if(KMPMatch()) printf("y\n");
			else printf("n\n");
		}
	}

	return 0;
}

Code: Select all

#include<stdio.h>
#include<string.h>
int pi[100001],len_st,len_t;
char st[100001],t[1001];
void prefix_function()
{
	int k=0,i;
	pi[0]=0;
	for(i=1;i<len_t;i++)
	{
		while(k>0&&t[k]!=t[i])
			k = pi[k];
		if(t[k]==t[i])
			k++;
		pi[i] = k;
	}
}
int main()
{
	bool found;
	int i,n,c,j;
	scanf("%d%*c",&n);
	while(n--)
	{
		gets(st);
		len_st = strlen(st);
		scanf("%d%*c",&c);
		while(c--)
		{
			gets(t);
			len_t = strlen(t);
			prefix_function();
			j=0;found=0;
			for(i=0;i<len_st;i++)
			{
				while(j>0&&t[j]!=st[i])
					j = pi[j];
				if(t[j]==st[i])
					j++;
				if(j==len_t-1){found = 1; break;}
			}
			if(found)puts("y");
			else puts("n");
		}
	}
	return 0;
}

Code: Select all

void prefix_function()
{
     int k = -1,i;
     pi[0] = -1;
     for(i = 1; i < len_t; i++)
     {
         while(k > -1 && t[k+1] != t[i])
             k = pi[k];
          if(t[k+1]==t[i])
             k++;
          pi[i] = k;
     }
}

Code: Select all

bool KMP_match(char txt[], chat pattern[])     // we search for "pattern" in "txt"
{
    int i = 0, j = 0;               // i - index of "txt" , j - index of "pattern"

    int tlen = strlen(txt), plen = strlen(pattern);

    while(1)
    {
       if(i==tlen) break;
       if(txt[i]==pattern[j])
       {
           ++i;
           ++j;
       }
       else if(j > 0)
       {
            j = pi[j-1] + 1;
       }
       else
           ++i;
       if(j==plen)
           return true;    // we have found a successful match :)  
    }
    return false;          // no match!!
}

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#define LLU long long unsigned int
#define LLD long long double
#define FOR(i,N) for(int i=0;i<(N);i++)
#define Vec vector<int>
#define Vit vector<int>::iterator

using namespace std;

int boyer_moore(char* sstr, char* pattern)

{

    char* inits = sstr;

    char* initp = pattern;



    int spatt = strlen(pattern);

    while(*pattern != '\0') pattern++;

    // this algorithm tested for printable ASCII characters

    // from ASCII, 65-90 and 97-122

    int* jump_table=(int*) calloc(128, sizeof(int));

    int count=0;



    while(pattern != initp) {

        pattern--;

        jump_table[*pattern]=count;

        count++;

    }



    char* stmp=0;

    char* iter=0;

    int shift=0;

    int bad_count=0;

    int bcount=0;

    while(*sstr != '\0')

    {

        bcount=0;

        bad_count=spatt;

        stmp = sstr+ (spatt-1);

        iter = pattern + (spatt-1);

        while(*stmp == *iter) {

            bad_count--;

            bcount++;

            stmp--;

            iter--;

            if(bcount==spatt)

                return sstr-inits;

        }



        //jump table

        if(jump_table[*stmp] == 0) {

            // the character not found in pattern

            shift=bad_count;

        } else {

            shift=jump_table[*stmp];

            (shift - bcount < 1)?shift = 1: shift = shift-bcount;

        }

        sstr += shift;

    }

    //not found

    return -1;

}







int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);

   int cases;
   cin>>cases;
getchar();
   while(cases--){

   char str[1000000];
   gets(str);
   int num;
   cin>>num;
    getchar();
   while(num--){

   char searc[1000000];
   gets(searc);
   int l=boyer_moore(str, searc);
if(l==-1)cout<<"n"<<endl;
else cout<<"y"<<endl;
   }
   }
    return 0;
}