Pagini recente » Cod sursa (job #1422541) | Cod sursa (job #613151) | Cod sursa (job #671050) | Cod sursa (job #2671496) | Cod sursa (job #1745629)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nmax = 2000005;
int N,M,pi[nmax],fans;
char a[nmax],b[nmax];
vector < int > ans;
inline void Pi()
{
int i,k;
k = 0;
pi[1] = 0;
for(i = 2; i <= N; i++)
{
while(k && a[k+1] != a[i]) k = pi[k];
if(a[k+1] == a[i]) k++;
pi[i] = k;
}
}
int main()
{
int i,k = 0;
fin >> (a+1) >> (b+1);
N = strlen(a+1), M = strlen(b+1);
Pi();
for(i = 1; i <= M; i++)
{
while(k && a[k+1] != b[i]) k = pi[k];
if(a[k+1] == b[i]) k++;
if(k == N && fans < 1000) ans.push_back(i - N), fans++;
else if(k == N) fans++;
}
fout << fans << "\n";
for(i = 0; i < ans.size(); ++i)
fout << ans[i] << " ";
fout.close();
return 0;
}