Pagini recente » Cod sursa (job #2676524) | Cod sursa (job #1015671) | Cod sursa (job #1889462) | Cod sursa (job #1060382) | Cod sursa (job #1228094)
#include <fstream>
#include <string.h>
#define lmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char N[lmax],M[lmax];
int n,m,k,nr;
int sol[lmax],prefix[lmax];
int main()
{
f>>N+1>>M+1;
N[0]=M[0]='a';
n=strlen(N)-1;
m=strlen(M)-1;
for (int i=2;i<=n;i++)
{
while (k>0 && N[k+1]!=N[i])
k=prefix[k];
if (N[k+1]==N[i])
k++;
prefix[i]=k;
}
k=0;
for (int i=1;i<=m;i++)
{
while (k>0 && N[k+1]!=M[i])
k=prefix[k];
if (N[k+1]==M[i])
k++;
if (k==n)
sol[++nr]=i-n;
}
g<<nr<<'\n';
for (int i=1;i<=nr;i++)
g<<sol[i]<<" ";
f.close();
g.close();
}