Pagini recente » Cod sursa (job #2325243) | Cod sursa (job #1422283) | Cod sursa (job #618338) | Cod sursa (job #1163813) | Cod sursa (job #2061410)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int Dim = 2000005;
char pattern[Dim], text[Dim];
int k, pi[Dim],rez[Dim],n,m,dim;
void prefix()
{
n = strlen(pattern+1);
k = 0;
for(int i=2; i<=n; i++)
{
while(k>0 && pattern[k+1]!=pattern[i])
k = pi[k];
if(pattern[k+1]==pattern[i])
k+=1;
pi[i] = k;
}
}
void kmp()
{
m = strlen(text+1);
k=0;
for(int i=1; i<=m; i++)
{
while(k>0 && pattern[k+1]!=text[i])
k = pi[k];
if(pattern[k+1]==text[i])
k+=1;
if(k==n)
{
k = pi[k];
dim+=1;
if(dim <= 1000)
rez[dim] = i-n;
}
}
}
int main()
{
f >> pattern+1 >> text+1;
prefix();
kmp();
g << dim << "\n";
dim = min(dim ,1000);
for(int i=1; i<=dim; i++)
g << rez[i] << ' ';
return 0;
}