Pagini recente » Cod sursa (job #889612) | Cod sursa (job #417950) | Cod sursa (job #1262600) | Cod sursa (job #583347) | Cod sursa (job #2416039)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX = 2 * (2 * 1e6 + 1e2);
int nsol;
int pref[1 + NMAX];
string s1;
string s2;
vector < int > res;
void precompute(string s)
{
int i = 0;
int j = 1;
pref[0] = 0;
while(j < s.size())
{
if(s[i] == s[j])
{
pref[j] = i + 1;
i++;
j++;
}
else
{
if(i > 0)
i = pref[i - 1];
else
{
pref[j] = 0;
j++;
}
}
}
}
int main()
{
in >> s1 >> s2;
precompute(s1 + '*' + s2);
for(int i = s1.size(); i < s1.size() + s2.size() + 1; i++)
{
if(pref[i] == s1.size())
{
nsol++;
if(nsol <= 1000)
{
res.push_back(i - 2 * s1.size());
}
}
}
out << nsol << '\n';
for(int i = 0; i < res.size(); i++)
out << res[i] << ' ';
out << '\n';
in.close();
out.close();
return 0;
}