Pagini recente » Cod sursa (job #427966) | Cod sursa (job #573814) | Cod sursa (job #2685314) | Cod sursa (job #1623170) | Cod sursa (job #3275943)
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n, cnt;
string a, b, s;
int z[4000005];
int ans[1005];
int main()
{
in>>a>>b;
s = a + '$' + b + '^';
n = s.size();
int l = 0;
int r = 0;
for(int i = 1; i<n; i++)
{
z[i] = max(0, min(r - i, z[i - l]));
while(s[z[i]] == s[i + z[i]])
{
z[i]++;
}
if(i + z[i] > r)
{
l = i;
r = i + z[i];
}
}
/*for(int i = 0; i<n; i++)
{
out<<s[i]<<" ";
}
out<<'\n';
for(int i = 0; i<n; i++)
{
out<<z[i]<<" ";
}*/
for(int i = a.size() + 1; i<n; i++)
{
if(z[i] == a.size())
{
cnt++;
if(cnt <= 1000)
{
ans[cnt] = i - a.size() - 1;
}
}
}
out<<cnt<<'\n';
for(int i = 1; i<=min(1000, cnt); i++)
{
out<<ans[i]<<" ";
}
return 0;
}