Pagini recente » Cod sursa (job #2909717) | Cod sursa (job #2038328) | Cod sursa (job #2616359) | Cod sursa (job #1479047) | Cod sursa (job #3030355)
#include <fstream>
#include <vector>
#include <cstring>
const int NMAX=2000005;
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[NMAX], t[NMAX];
int n, m, pi[NMAX], d[NMAX];
vector <int> ans;
void pii(char []);
int main()
{
int i, k=-1;
fin>>s>>t;
n=strlen(s);
m=strlen(t);
pii(s);
for(i=0; i<m; i++)
{
while(k>0 && t[i]!=s[k+1]) k=pi[k];
if(t[i]==s[k+1]) k++;
d[i]=k;
if(k==n-1) ans.push_back(i-n+1);
}
fout<<ans.size()<<'\n';
for(auto i:ans) fout<<i<<' ';
return 0;
}
void pii(char s[])
{
int k=-1, i;
pi[0]=0;
for(i=1; i<n; i++)
{
while(k>0 && s[i]!=s[k+1]) k=pi[k];
if(s[i]==s[k+1]) k++;
pi[i]=k;
}
}