Pagini recente » Cod sursa (job #1756685) | Cod sursa (job #2569057) | Cod sursa (job #2322741) | Cod sursa (job #1246539) | Cod sursa (job #2416893)
#include <string>
#include <fstream>
#include <vector>
using namespace std;
vector <int> sol, z(4000005);
string a, b, c;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> a >> b;
c = a + "$" + b;
int left = 0, right = 0;
for (int i = 1;i < c.length();++i)
{
if (i > right)
{
left = right = i;
while (right < c.length() && c[right] == c[right - left])
++right;
z[i] = right - left;
--right;
}
else
{
int p = i - left;
if (z[p] < right - i + 1)
z[i] = z[p];
else
{
left = i;
while (right < c.length() && c[right] == c[right - left])
++right;
z[i] = right - left;
--right;
}
}
}
int cnt = 0;
for (int i = a.length();i < c.length();++i)
{
if (z[i] == a.length())
{
++cnt;
if (cnt <= 1000)
sol.push_back(i - a.length() - 1);
}
}
fout << cnt << "\n";
for (int i = 0;i < sol.size();++i)
fout << sol[i] << " ";
fin.close();
fout.close();
return 0;
}