Pagini recente » Cod sursa (job #1030566) | Istoria paginii runda/jc2018-runda-2 | Cod sursa (job #1298864) | Cod sursa (job #2428543) | Cod sursa (job #2563487)
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string pat, str;
int z[4000010];
void zBuild(string x)
{
int L = 0, R = 0, k;
int n = x.size();
for(int i = 1; i <= n; i++)
{
if(i > R)
{
L = R = i;
while(R <= n && x[R - L] == x[R])
R++;
z[i] = R - L;
R--;
}
else
{
k = i - L;
if(z[k] < R - i + 1)
z[i] = z[k];
else
{
L = i;
while(R <= n && x[R - L] == x[R])
R++;
z[i] = R - L;
R--;
}
}
}
}
void solve()
{
string concat = pat + '$' + str;
queue<int> q;
int limit = 1000;
zBuild(concat);
for(int i = 0; i < concat.size() && q.size() < limit; i++)
if(z[i] == pat.size())
q.push(i - pat.size() - 1);
out << q.size() << '\n';
while(!q.empty())
{
out << q.front() << ' ';
q.pop();
}
}
int main()
{
in >> pat >> str;
solve();
return 0;
}