Pagini recente » Cod sursa (job #447265) | Cod sursa (job #3277026) | Cod sursa (job #2924199) | Cod sursa (job #1142194) | Cod sursa (job #2976305)
#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++)
// {
// while(c && a[i] != a[c])
// c = t[c];
// if(a[i] == a[c])
// c++;
// t[i] = c;
// }
int c = 0;
for(int i = 1; i<strlen(a); i++)
{
while(c && a[i] != a[c])
c = t[c-1];
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;
while(j && b[i] != a[j])
j = t[j-1];
j++;
if(j == strlen(a))
{
// out<<"found"<<endl;
p[ct++] = i - strlen(a) + 1;
j = t[j-1];
}
}
show();
return 0;
}