Pagini recente » Cod sursa (job #2673636) | Cod sursa (job #803297) | Cod sursa (job #1782110) | Cod sursa (job #2096454) | Cod sursa (job #2238594)
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,t;
vector <int> sol;
int q,n,m,i,pr[NMAX],cnt;
int main()
{
f>>s>>t;
n=s.size();
m=t.size();
s='#'+s;
t='#'+t;
for(i=2; i<=n; i++)
{
while(q&&s[i]!=s[q+1])
q=pr[q];
if(s[i]==s[q+1])
q++;
pr[i]=q;
}
q=0;
for(i=1; i<=m; i++)
{
while(q&&t[i]!=s[q+1])
q=pr[q];
if(t[i]==s[q+1])
q++;
if(q==n)
{
q=pr[q];
if(cnt<1000)
sol.push_back(i-n);
cnt++;
}
}
g<<cnt<<'\n';
for(auto it:sol)
g<<it<<' ';
return 0;
}