Pagini recente » Cod sursa (job #1778571) | Cod sursa (job #2433399) | Cod sursa (job #691724) | Cod sursa (job #584847) | Cod sursa (job #3247582)
#include <bits/stdc++.h>
const std :: string FILENAME = "strmatch";
std :: ifstream f (FILENAME + ".in");
std :: ofstream g (FILENAME + ".out");
const int NMAX = 2e6 + 5;
int cnt;
int z[2 * NMAX];
std :: string a;
std :: string b;
std :: string s;
void _z(const std :: string & s)
{
int l = 0;
int r = 0;
for(int i = 1; i < s.size(); i ++)
{
if(i < r)
{
z[i] = std :: min(r - i, z[i - l]);
}
while(s[z[i]] == s[i + z[i]])
{
z[i] ++;
}
if(r < i + z[i])
{
r = i + z[i];
l = i;
}
}
}
int main()
{
f >> a >> b;
s = a + "*" + b;
_z(s);
for(int i = 0; i < s.size(); i ++)
{
if(z[i] == a.size())
{
cnt ++;
}
}
g << cnt << '\n';
cnt = 0;
for(int i = 0; i < s.size(); i ++)
{
if(z[i] == a.size())
{
cnt ++;
g << i - a.size() - 1 << " ";
if(cnt == 1000)
{
return 0;
}
}
}
return 0;
}