Pagini recente » Cod sursa (job #1637206) | Cod sursa (job #2048111) | Cod sursa (job #3129244) | Cod sursa (job #106247) | Cod sursa (job #1745595)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMax = 2000005;
char s[NMax],P[NMax];
int n,m,i,j,q,k,stare[NMax],nr;
vector <int> sl;
void prefix()
{
stare[1] = 0;
k = 0;
for(q = 2; q <= m; q++)
{
while(k > 0 && P[k + 1] != P[q])
k = stare[k];
if(P[k + 1] == P[q])
k++;
stare[q] = k;
}
}
void kmp()
{
prefix();
q = 0;
for(i = 1; i <= n; i++)
{
while(q > 0 && P[q + 1] != s[i])
q = stare[q];
if(P[q + 1] == s[i])
q++;
if(q == m)
{
nr++;
if(nr<=1000)
sl.push_back(i - m);
q = stare[q];
}
}
}
int main()
{
fin.get(P+1,2000001);
fin.get();
fin.get(s+1,2000001);
n = strlen(s+1);
m = strlen(P+1);
kmp();
fout<<nr<<'\n';
for(i = 0 ; i < sl.size(); i++)
fout<<sl[i]<<" ";
return 0;
}