Pagini recente » Cod sursa (job #1482198) | Cod sursa (job #2394859) | Cod sursa (job #752116) | Cod sursa (job #2393404) | Cod sursa (job #1767493)
#include <fstream>
#include <vector>
#define nmax 3000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> sol;
string a, b, rez;
int z[nmax],n,j,k,i;
int main()
{
fin>>a>>b;
string rez = "0";
rez+=a;rez+='#';rez+=b;
n = rez.length() - 1;
k=1;
for (i = 2; i <= n; ++i)
{
if (k + z[k] - 1 < i)
{
int p = i;
for (j=1;p<=n && rez[p]==rez[j];++p,++j);
z[i]=p-i;
k=i;
}
else
{
z[i] = min(z[i - k + 1], k + z[k] - 1 - (i - 1));
for (; z[i] + i <= n && rez[z[i] + i] == rez[z[i] + 1]; ++z[i]);
if (i + z[i] - 1 > k + z[k] - 1)
{
k = i;
}
}
}
for (int i = a.length() + 1; i <= n; ++i)
{
if (z[i] >= a.length())
{
sol.push_back(i - a.length() - 2);
}
}
fout << sol.size() << '\n';
for (int i = 0; i < min(1000,int (sol.size())); ++i)
{
fout << sol[i] << ' ';
}
return 0;
}