Pagini recente » Cod sursa (job #427687) | Borderou de evaluare (job #105364) | Cod sursa (job #759758) | Cod sursa (job #1960335) | Cod sursa (job #1225903)
#include <iostream>
#include <fstream>
using namespace std;
ifstream ka("strmatch.in");
ofstream ki("strmatch.out");
const int A_MAX = 2000000;
string a, b;
int t[A_MAX + 1], raspuns, sol[1001];
void precompute()
{
int cand = 0;
t[0] = -1;
t[1] = 0;
int i = 2;
while(i < a.size())
{
if(a[i-1] == a[cand])
{
cand++;
t[i] = cand;
i++;
}
else if(cand > 0)
cand = t[cand];
else
{
t[cand] = 0;
i++;
}
}
}
int main()
{
getline(ka, a);
getline(ka, b);
precompute();
int cand = 0;
int m = 0;
while(m + cand < b.size())
{
if(a[cand] == b[m+cand])
{
if(cand == a.size() - 1)
{
raspuns++;
if(raspuns <= 1000)
sol[++sol[0]] = m;
}
else
cand++;
}
else
{
if(t[cand] > -1)
{
m = m + cand - t[cand];
cand = t[cand];
}
else
{
cand = 0;
m++;
}
}
}
ki << raspuns << '\n';
for(int i = 1; i <= sol[0]; i++)
ki << sol[i] << " ";
}