Pagini recente » Cod sursa (job #96205) | Cod sursa (job #1753610) | Cod sursa (job #740402) | Cod sursa (job #1251793) | Cod sursa (job #3030365)
#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], a[NMAX];
int n, m, pi[NMAX], d[NMAX];
vector <int> ans;
void pii(char []);
int main()
{
int i, k=0;
fin>>a;
for(i=0; a[i]; i++) s[i+1]=a[i];
n=i;
fin>>a;
for(i=0; a[i]; i++) t[i+1]=a[i];
m=i;
pii(s);
for(i=1; 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) ans.push_back(i-n);
}
fout<<ans.size()<<'\n';
for(auto i:ans) fout<<i<<' ';
return 0;
}
void pii(char s[])
{
int k=0, i;
pi[1]=0;
for(i=2; i<=n; i++)
{
while(k>0 && s[i]!=s[k+1]) k=pi[k];
if(s[i]==s[k+1]) k++;
pi[i]=k;
}
}