Pagini recente » Cod sursa (job #2341655) | Cod sursa (job #2341027) | Cod sursa (job #3038143) | Cod sursa (job #514887) | Cod sursa (job #2976297)
#include<bits/stdc++.h>
using namespace std;
const int N = 2000009;
char a[N], b[N];
int 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<strlen(a); i++)
if(a[i] == a[c])
t[i] = ++c;
else
c = 0;
}
void debug_t()
{
for(int i = 0; i<strlen(a); i++)
out<<t[i]<<' ';
out<<endl;
}
void show()
{
out<<ct<<endl;
for(int i=0;i<ct;i++)
out<<p[i]<<' ';
out<<endl;
}
int main(){
in>>a>>b;
build();
// debug_t();
int j=0;
for(int i=0; i<strlen(b); i++)
{
// out<<"i: "<<i<<"; j: "<<j<<endl;
if(b[i] == a[j])
j++;
else
j = t[j];
if(j == strlen(a))
{
// out<<"found"<<endl;
p[ct++] = i - strlen(a) + 1;
j = t[j-1];
}
}
show();
return 0;
}