coding_codes/kmp.cpp at master · ranarag/coding_codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int MAX = 1e4+5;
int f[MAX];
int l;
char p[MAX];
void init()
{
	for(int i=0;i<=l;i++)f[i]=0;
}
void failure_function()
{
	//int l = strlen(p);
	init();
	int j=0;
	for(int i=1;i<l;i++)
	{
		while(j>=0&&p[j]!=p[i])
		{
			if(j-1>=0)
				j = f[j-1];
			else
				j = -1;
		}
		j += 1;
		f[i] = j;
	}

}
void find_occurrences()
{
	failure_function();
	int lp = l;
	char c=getchar();
	int j=0,i=0;
	while((c = getchar())!='\n')
	{
		if(c==EOF)
		exit(1);
		while(j>=0&&c!=p[j])
		{
			if(j-1>=0)
				j = f[j-1];
			else
				j = -1;
		}
		j+=1;
		if(j==lp)
		{
			j = f[lp-1];
			cout<<i-lp+1<<endl;
		}
		i++;
	}
	if(c==EOF)
		exit(1);

}
int main(void)
{
	while(1)
	{
	scanf("%d",&l);
	scanf("%s",p);

	find_occurrences();
	}
}