Pagini recente » Cod sursa (job #1124314) | Cod sursa (job #2041543) | Cod sursa (job #3031176) | Cod sursa (job #2847891) | Cod sursa (job #1311769)
#include <cstdio>
#include <cstring>
#include <vector>
#include <fstream>
#define pb push_back
#define max_dim 2000010
using namespace std;
vector<int> positions;
char a[max_dim], b[max_dim];
int nxt[max_dim];
int n, m, i, q, k;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a+1; f>>b+1;
n=strlen(a+1); m=strlen(b+1);
q=0; nxt[1]=0;
for(i=2; i<=n; ++i)
{
while(a[i]!=a[q+1] && q!=0)
q=nxt[q];
if(a[i]==a[q+1])
++q;
nxt[i]=q;
}
q=0;
for(i=1; i<m; ++i)
{
while(b[i]!=a[q+1] && q!=0)
q=nxt[q];
if(b[i]==a[q+1])
++q;
if(q==n)
{
if(positions.size()<=1000) positions.pb(i-n);
q=nxt[q];
}
}
g<<positions.size()<<"\n";
vector<int>::iterator it;
for(it=positions.begin(); it!=positions.end(); ++it)
g<<*it<<" ";
return 0;
}