Pagini recente » Cod sursa (job #2321372) | Cod sursa (job #156520) | Cod sursa (job #290714) | Cod sursa (job #406670) | Cod sursa (job #2012509)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char text[2000001], pattern[2000001];
int index[1001], k, lps[2000001];
void compute_LPS_array (int m)
{
int len = 0;
int i = 1;
while ( i < m )
{
if ( pattern[i] == pattern[len] )
{
len++;
lps[i] = len;
i++;
}
else
{
if ( len != 0)
len = lps[len-1];
else
{
lps[i] = 0;
i++;
}
}
}
}
void kmp_search (int n, int m)
{
compute_LPS_array (m);
int i = 0, j = 0;
while ( i < n)
{
if ( pattern[j] == text[i] )
{
i++;
j++;
}
if ( j == m)
{
k++;
index[k] = i - j;
j = lps[j-1];
}
else
if ( i < n && pattern[j] != text[i])
{
if (j != 0)
j = lps[j-1];
else
i++;
}
}
fout<<k<<"\n";
for ( int i = 1; i <= k; ++i )
fout<<index[i]<<" ";
}
int main()
{
int n, m;
fin>>pattern;
fin>>text;
n = strlen(text);
m = strlen(pattern);
kmp_search (n, m);
}