Pagini recente » Cod sursa (job #2563778) | Cod sursa (job #3247105) | Cod sursa (job #175995) | Cod sursa (job #67931) | Cod sursa (job #2849395)
///#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int SIZE = 2e6+10;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char s1[SIZE], s2[SIZE];
int s1n, s2n;
int pre[SIZE];
int cnt;
vector <int> rez;
void getPre()
{
int i, j;
for(j=2, i=1; j<=s2n; j++)
if(s2[j]==s2[i]) {
pre[j] = i++;
}
else {
while(i && s2[i]!=s2[j]) i=pre[i];
if(!i) i++;
if(s2[j]==s2[i]) pre[j] = i++;
}
}
int main()
{
cin>>(s2+1)>>(s1+1);
s1n = strlen(s1+1);
s2n = strlen(s2+1);
getPre();
int i, j;
for(i=1, j=0; i<=s1n; i++) {
if(s1[i]==s2[j+1]) {
++j;
if(j==s2n) {
++cnt;
j=pre[j];
if(rez.size()<1000) rez.push_back(i-s2n);
}
}
else {
while(j && s1[i]!=s2[j+1]) j=pre[j];
if(s1[i]==s2[j+1]) ++j;
}
}
cout<<cnt<<'\n';
for(auto i : rez) cout<<i<<' ';
return 0;
}