Pagini recente » Monitorul de evaluare | Cod sursa (job #382477) | Clasament cerc_info_2011_01 | Cod sursa (job #772038) | Cod sursa (job #2553032)
#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();
cout<<sol.size()<<'\n';
for(int i=0; i<sol.size(); ++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;
}
}
}
}