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