Pagini recente » Cod sursa (job #1377534) | Cod sursa (job #784669) | Cod sursa (job #2923653) | Cod sursa (job #2625916) | Cod sursa (job #2553035)
#include <bits/stdc++.h>
#define cin fin
#define cout fout
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m;
char pattern[NMAX], s[NMAX];
int lps[NMAX];
vector<int> sol;
void process();
void kmp();
int main()
{
cin>>pattern>>s;
n=strlen(s);
m=strlen(pattern);
process();
kmp();
int temp=sol.size();
cout<<temp<<'\n';
for(int i=0; i<min(temp, 1000); ++i)
cout<<sol[i]<<' ';
return 0;
}
void kmp()
{
int i=0, j=0;
while(i<n)
{
if(s[i]==pattern[j])
{
++i;
++j;
if(j==m)
{
sol.push_back(i-j);
j=lps[j-1];
}
}
else
{
if(j>0)
j=lps[j-1];
else ++i;
}
}
}
void process()
{
int len=0;
lps[0]=0;
int i=1;
while(i<m)
{
if(pattern[i]==pattern[len])
{
++len;
lps[i]=len;
++i;
}
else
{
if(len!=0)
len=lps[len-1];
else
{
lps[i]=0;
++i;
}
}
}
}