Pagini recente » Cod sursa (job #1492917) | Cod sursa (job #2735221) | Cod sursa (job #2002763) | Cod sursa (job #740176) | Cod sursa (job #1409700)
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#define ull unsigned long long
#define ll long long
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int N,M,i,k,nrap;
int pi[2000005];
int poz[1005];
char strM[2000005],strN[2000005];
int main()
{
f>>(strN+1)>>(strM+1);
M=strlen(strM+1);
N=strlen(strN+1);
//cout<<N<<'\n';
k=0;
pi[1]=0;
for (i=2;i<=N;++i)
{
while (k>0 && strN[k+1]!=strN[i])
k=pi[k];
if (strN[k+1]==strN[i]) // se calculeaza p[i],
++k; // p[i]= lungimea maxima a unui prefix al sirului N,
pi[i]=k; // care e si sufix pentru prefixul de lungime i;
}
k=0;
for (i=1;i<=M;++i)
{
while (k>0 && strN[k+1]!=strM[i])
k=pi[k];
if (strN[k+1]==strM[i])
++k;
if (k==N)
{
++nrap;
if (nrap<=1000)
poz[nrap]=i-N;
}
}
g<<nrap<<'\n';
if (nrap>1000)
nrap=1000;
for (i=1;i<=nrap;++i)
g<<poz[i]<<' ';
f.close();g.close();
return 0;
}