Pagini recente » Cod sursa (job #1986835) | Cod sursa (job #2395125) | Cod sursa (job #1760855) | Cod sursa (job #2981834) | Cod sursa (job #2153937)
#include <bits/stdc++.h>
#define scooby_doo(a, b) ((a<b) ? a : b)
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s;
string v;
int k,nr,pi[2000001],ns,nv,pos[1001];
void prefixe()
{
int k=0;
pi[1]=0;
for(int i=2; i<=ns; ++i)
{
while(k && s[k+1] != s[i])k=pi[k];
if(s[k+1]==s[i])++k;
pi[i]=k;
}
}
int main()
{
getline(f,s);
getline(f,v);
ns=s.length();
nv=v.length();
for(int i=ns; i; --i)s[i]=s[i-1];
s[0]=' ';
for(int i=nv; i; --i)v[i]=v[i-1];
v[0]=' ';
prefixe();
for(int i=1; i<=nv; ++i)
{
while(k && s[k+1] != v[i])k=pi[k];
if(s[k+1] == v[i])++k;
if(k==ns)
{
k=pi[ns];
nr++;
if(nr<=1000)pos[nr]=i-ns;
}
}
g<<nr<<'\n';
for(int i=1;i <= scooby_doo(nr, 1000); ++i)g<<pos[i]<<' ';
return 0;
}