Pagini recente » Cod sursa (job #3030367) | Cod sursa (job #2709071) | Cod sursa (job #3157043) | Cod sursa (job #2072088) | Cod sursa (job #3038091)
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pat, text;
int n, m;
int v[2000005];
int w[1005];
int ind = 0;
void build_lps()
{
v[0] = 0;
int i = 1;
int len = 0;
while(i < m)
{
if(pat[i] == pat[len])
{
len++;
v[i] = len;
i++;
}
else
{
if(len != 0)
{
len = v[len-1];
}
else
{
v[i] = 0;
i++;
}
}
}
}
void kmp()
{
int i = 0;
int j = 0;
while((n-i) >= (m-j))
{
if(pat[j] == text[i])
{
j++;
i++;
}
if(j == m)
{
ind++;
if(ind <= 1000)
{
w[ind] = i-j;
}
j = v[j-1];
}
else if(i < n && pat[j] != text[i])
{
if(j != 0)
{
j = v[j-1];
}
else
{
i++;
}
}
}
}
int main()
{
f>>pat>>text;
m = pat.length();
n = text.length();
build_lps();
kmp();
g<<ind<<'\n';
for(int i = 1; i<=min(ind, 1000); i++)
{
g<<w[i]<<" ";
}
return 0;
}