Pagini recente » Statistici Ana-Malina Munteanu (Ana-Malina) | Istoria paginii utilizator/panainte_theodora | Profil unibucPoli2019 | Cod sursa (job #2017208) | Cod sursa (job #1169764)
#include <fstream>
#include <cstring>
#define mn(a,b) ((a<b) ? a : b)
using namespace std;
char S1[2000003],S1p[2000003];
char S2[2000003],S2p[2000003];
int N,M,i,k,pi[2000003],v[2000003],nr;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.get(S1p,2000002);f.get();
f.get(S2p,2000002);f.get();
strcat(S1,"%");
strcat(S2,"%");
strcat(S1,S1p);
strcat(S2,S2p);
N=strlen(S1);
M=strlen(S2);
N--;M--;
for (i=2;i<=N;i++)
{
while ((k) && S1[i]!=S1[k+1]) k=pi[k];
if (S1[i]==S1[k+1]) k++;
pi[i]=k;
}
k=0;
for (i=1;i<=M;i++)
{
while ((k) && S2[i]!=S1[k+1]) k=pi[k];
if (S2[i]==S1[k+1]) k++;
if (k==N) v[++nr]=i-N;
}
g<<nr<<'\n';
for (i=1;i<=mn(nr,1000);i++) g<<v[i]<<" ";
f.close();
g.close();
return 0;
}