Pagini recente » Cod sursa (job #288657) | Cod sursa (job #2553942) | Cod sursa (job #2173823) | Cod sursa (job #470665) | Cod sursa (job #2976326)
#include<bits/stdc++.h>
using namespace std;
const int N = 2000009;
char a[N], b[N];
int la, lb, t[N], p[N], ct;
ifstream in ("strmatch.in");
ofstream out("strmatch.out");
// auto& in = cin;
// auto& out = cout;
void build()
{
int c = 0;
for(int i = 1; i<la; i++)
{
while(c && a[i] != a[c])
c = t[c-1];
if(a[i] == a[c])
c++;
t[i] = c;
}
}
void show()
{
out<<ct<<endl;
for(int i=0;i<min(1000,ct);i++)
out<<p[i]<<' ';
out<<endl;
}
int main(){
in>>a>>b;
la = strlen(a);
lb = strlen(b);
build();
int j=0;
for(int i=0; i<lb; i++)
{
while(j && b[i] != a[j])
j = t[j-1];
if(b[i] == a[j])
j++;
if(j == la)
{
p[ct++] = i - la + 1;
j = t[j-1];
}
}
show();
return 0;
}