Pagini recente » Cod sursa (job #524729) | Cod sursa (job #2723445) | Cod sursa (job #1254394) | Cod sursa (job #24826) | Cod sursa (job #1638558)
#include <fstream>
#include <string.h>
#include <vector>
#define nMax 2000005
#define pb push_back
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int p[nMax], k, n, m, nrSol;
char A[nMax], B[nMax];
vector<int> Sol;
void read()
{
fin>>A+1>>B+1;
n=strlen(A+1), m=strlen(B+1);
}
void prefix()
{
for(int i=2;i<=n;i++)
{
while(k && A[k+1]!=A[i])
k=p[k];
if(A[k+1]==A[i])
k++;
p[i]=k;
}
}
void solve()
{
prefix();
k=0;
for(int i=1;i<=m;i++)
{
while(k && A[k+1]!=B[i])
k=p[k];
if(A[k+1]==B[i])
k++;
if(k==n)
{
if(Sol.size()<1000)
Sol.pb(i-n);
nrSol++;
k=p[k];
}
}
}
void write()
{
fout<<nrSol<<'\n';
for(vector<int>::iterator it=Sol.begin();it!=Sol.end();it++)
fout<<*it<<" ";
}
int main()
{
read();
solve();
write();
return 0;
}