Pagini recente » Cod sursa (job #2750541) | Cod sursa (job #1660702) | Cod sursa (job #2702754) | Cod sursa (job #1959792) | Cod sursa (job #1338296)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char x[2000001], y[2000001];
int l[2000001], k, m, n, nra, poz[1001];
void read()
{
f >> x + 1;
f >> y + 1;
x[0] = ' ';
y[0] = ' ';
}
void contstruct()
{
n = strlen(x) - 1;
m = strlen(y) - 1;
l[1] = 0;
k = 0;
for(int i = 2; i<=n; i++)
{
while(k > 0 && x[i] != x[k + 1])
k = l[k];
if(x[i] == x[k + 1]) k++;
l[i] = k;
}
}
void solve()
{
k = 0;
for(int i = 1; i<=m; i++)
{
while(k > 0 && y[i] != x[k + 1])
k = l[k];
if(y[i] == x[k + 1]) k++;
if(k == n)
{
nra ++;
if(nra <= 100)
poz[nra] = i - n;
}
}
g << nra << '\n';
}
int main()
{
read();
contstruct();
solve();
if(nra <= 1000)
for(int i = 1; i<= nra; i++)
g << poz[i] << ' ';
else for(int i = 1; i<=1000; i++)
g << poz[i] << ' ';
return 0;
}