Pagini recente » Cod sursa (job #2128408) | Cod sursa (job #3270012) | Cod sursa (job #2810454) | Cod sursa (job #2469369) | Cod sursa (job #2653542)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string s;
string a, b;
unsigned int p[4000000 + 7];
int main()
{
in >> a >> b; //s = '*' + a + '*' + b;
s.resize(2 + a.size() + b.size());
s[0] = '*';
for(int i = 1; i <= a.size(); i++)
s[i] = a[i-1];
s[a.size()+1] = '*';
for(int i = a.size()+2; i < s.size(); i++)
s[i] = b[i - a.size() - 2];
//cout << s << endl;
unsigned int k = 0;
for(unsigned int i = 2; i < s.size(); i++)
{
while(k > 0 && s[k+1] != s[i])
k = p[k];
if(s[k+1] == s[i])
k++;
p[i] = k;
}
int nr_ap = 0;
for(unsigned int i = 0; i < s.size(); i++)
{
//cout << p[i] << endl;
if(p[i] == a.size())
nr_ap++;
}
out << nr_ap << endl;
if(nr_ap > 1000) nr_ap = 1000;
for(unsigned int i = 0; i < s.size(); i++)
{
if(p[i] == a.size() && nr_ap--)
out << i - 1 - 2*a.size() << " ";
}
}